首先容易发现若某个 i 满足 \forall j\le i,p_j\le i，则 [1,i] 与 [i+1,n] 之间不可能相互到达，所以整个图被分成两个连通块。找到所有这样的 i 就能将图分为若干连通块，对每个连通块分别计算答案即可，下面假设整个排列连通，考虑如何计算答案。
由于最短路本身并没有什么比较好的性质，所以对每个 x 求 i 与 x 之间的最短路不太现实。因此考虑将 \displaystyle\sum_x dis(i,x) 转化为 \displaystyle\sum_t\sum_x[dis(i,x)\ge t]，即对于每个 t 计算最短路至少为 t 的点的数目求和。那么我们从 1 开始先手动分析一下满足 dis(i,x)\ge t 的点要满足什么性质。这里由于左右两侧是对称的，所以现在只考虑 x<i 的情形，另一侧将排列翻转之后再做一次即可。
当 t=1 时，由于整个排列连通，所以显然答案是 i-1。
当 t=2 时，所有满足 j<i,p_j<p_i 的点都不能一次被到达。
当 t=3 时，考虑一个点 j 什么时候能在两步之内到达。假设第一步向左走，则一定是走到最左侧的一个点最优。假设最左侧能到达 l，但 l 下一步不能到达 j，而存在另一个点 x 能够到达 j。由于 x 能一步到达 j，而 i 一步无法到达 j，所以此时满足 x<j<i 且 p_x>p_i>p_j。然而 l<x,p_l>p_i，所以 l 也可以一步到达 j，矛盾。类似地，可以证明若第一步向右走，则一定是走到 p_x 最小的点最优。这样只需要求出最左能到达的点 l 和最右能到达的点 r，那么若 j 既不能被 l 到达，也不能被 r 到达，则 dis(i,j)\ge 3。这个条件相当于 j<l 且 p_j<p_r。
类似上一种情况继续探索 t=4,5 时的最优策略可以发现，如果不是一步可以到达，从一个点要么走到左侧最靠左的点，要么走到右侧最靠下（即 p 最小）的点。并且若前一次走最左侧的点，那么下一次一定走最下侧的点（否则只能走到它自己）。而这样能够走到的两个点对应了所有不能走到的点的一个右边界和上边界，所以这是一个比较好的形式。具体来说，记 u_i 表示 i 向左能走到的最左侧的点，d_i 表示 i 向右能走到的最下侧的点，那么如果用 (a_t,b_t) 表示 dis(i,j)\ge t 时需要满足 j<a_t,p_j<b_t，可以得出结论：(a_2,b_2)=(i,i)，(a_{t+1},b_{t+1})=(u_{b_t},d_{a_t})(t\ge2)。所以一个暴力的做法就是求出 u,d 之后枚举 t，然后一次对答案的贡献形如一个矩形的元素个数，可以预处理，复杂度 O(n^2)。