実装面の解説は最後の \(2\) 段落に記載されています。二分木上の動的計画法に帰着できることを理解している場合はそちらをお読みください。

この問題を動的計画法で解くことを考えます。
猫が現在タワー \(i\) \((1\leq i\leq N)\)におり、そこから隣接するタワーへの移動を繰り返して到達できるタワーの範囲がタワー \(l,l+1,\ldots,r\) \((1\leq l\leq i\leq r\leq N)\)である状態を状態 \((i,l,r)\) と定義します。状態 \((i,l,r)\) から、運動が終了するまでの猫の移動距離の合計の最大値は、それまでの過程等によらず一意に定まります。この値を \(dp[(i,l,r)]\) とします。
求めたい答えは、高さが \(N\) のタワーをタワー \(k_0\) として、\(dp[(k_0,1,N)]\) です。

ここで、初期状態 \((k_0,1,N)\) からの（直接でなくても良い）遷移先 \((i,l,r)\) は次の条件をみたしている必要があります。

• \(P_l,P_{l+1},\ldots, P_r\) はすべて \(P_i\) 以下である。

これは、猫が最初に最も高い（高さ \(N\) の）タワーいる事および移動方法の定義より、タワーを撤去していく過程においてつねに「猫が高さ \(k\) のタワーにいる時、そのタワーから始めて隣接するタワーへの移動を繰り返して到達できるタワーの高さはすべて \(k\) 以下である。」という事実が成り立つことから従います。

ここで、\(1\leq k\leq N\) に対して、\([L_k,R_k]\) を、\(1\leq L_k\leq k \leq R_k\leq N\) かつ、\(L_k\leq i\leq R_k\) ならば \(P_i\leq P_k\) をみたす極大な区間として定義します。すなわち、

• \(i<k\) かつ \(P_i>P_k\) をみたす \(i\) が存在するならば、そのうち最大の \(i\) について \(L_k=i+1\) 、そうでないならば \(L_k=1\)
• \(k<j\) かつ \(P_j>P_k\) をみたす \(j\) が存在するならば、そのうち最小の \(j\) について \(R_k=j-1\)、そうでないならば \(R_k=N\)

です。このように定義した時、先の事実より、\(L_i\leq l\leq i\leq r\leq R_i\) をみたす状態 \((i,l,r)\) についてのみ考えれば十分です。
さらに、このような状態 \((i,l,r)\) はすべて、状態 \((i,L_i,R_i)\) から遷移可能な（必要であればタワー \(l-1\) と \(r+1\) を撤去すれば良い ）ことに注意すると、\(dp[(i,L_i,R_i)]\geq dp[(i,l,r)]\) が成り立ちます。

次に、以下の事実を示します。

ある \((l,r)\) \((L_i\leq l\leq i\leq r\leq R_i)\) が存在して、状態 \((i,l,r)\) からタワー \(i\) を撤去することで（直接）状態 \((j,l',r')\) へ遷移する場合、状態 \((i,L_i,R_i)\) から適切に操作を行うことで状態 \((j,L_j,R_j)\) へ遷移させることができる。

主張前半のようなことができる必要条件は \(L_i\leq j\leq R_i\) かつ、タワー \(j\)とタワー \(i\) の間（タワー \(j,j+1,\ldots,i\) または \(i,i+1,\ldots,j\)）の間に高さ \(P_j\) 以上のタワーが存在しないことです。そうでない場合、タワー \(i\) を撤去してタワー \(j\) へ移動させることは不可能です。逆にこれが成り立つ時、後者をみたすような操作が可能です。対称性より \(j<i\) のときに具体的な操作を示せば十分です。これは、（\(L_i<L_j\) ならば）タワー \(L_j-1\) および（\(i<R_i\) ならば）タワー \(i+1\) を撤去してからタワー \(R_j+1\)（条件より \(R_j+1=i\) ）を撤去すれば良いです。

さて、このとき、状態 \((i,L_i,R_i)\to (i,l,r)\to (j,l',r')\) と遷移した時の運動の合計の最大値が\( dp[(j,l',r')]+\lvert i-j\rvert\) であり、\((i,L_i,R_i)\to (j,L_j,R_j)\) と遷移した時の運動の合計の最大値が\( dp[(j,L_j,R_j)]+\lvert i-j\rvert\) であり、後者の方がつねに大きいことからこのような状態の間の遷移のみ考えれば良い、すなわち、状態 \((i,L_i,R_i)\) \((1\leq i\leq N)\) のみを対象として考えれば十分であることが分かります。

さらに、タワー \(L_i,L_i+1,\ldots, i-1\) の中で最も高いタワーを \(M^L_i\), タワー \(i+1, i+2,\ldots, R_i\) の中で最も高いタワーを \(M^R_i\) とすると、次の事実が成り立ちます。

状態 \((i,L_i,R_i)\) から状態 \((j,L_j,R_j)\) に遷移可能な時、 \(j<i\) ならば状態 \((M^L_i,L_{M^L_i},R_{M^L_i})\) から、 \(i<j\) ならば状態 \((M^R_i,L_{M^R_i},R_{M^R_i})\) からそれぞれ遷移可能である。

対称性より、\(j<i\) のときに状態 \((M^L_i,L_{M^L_i},R_{M^L_i})\) から遷移可能なことを示せば十分です このことは次の \(3\) 点から成り立ちます。

• \(L_{M^L_i}\leq j\leq R_{M^L_i}\)　が成り立つ。
• 任意の \(i'\) および \(L_{i'}\leq j'\leq R_{i'}\) について、適当な \((l,r)\) が存在して、状態 \((i',L_{i'},R_{i'})\) から状態 \((j',l,r)\) へ遷移可能である。
• ある \(l,r,l',r'\) が存在して、状態 \((i',l,r)\) から状態 \((j',l',r')\) へ遷移できる場合、状態 \((i',L_{i'},R_{i'})\) から状態 \((j',L_{j'},R_{j'})\) へ遷移可能である。

\(1\) 点目は定義より従います。 \(2\) 点目については、現在猫がいるタワーから見て、タワー \(j'\) を含まない側のタワーをすべて撤去してから現在いるタワーを撤去することを繰り返すことで有限回の操作で達成可能です。 \(3\) 点目はすでに示した直接遷移する場合を繰り返し適用することで従います。

示された事実より、状態 \((i,L_i,R_i)\) から、状態 \((M^L_i,L_{M^L_i},R_{M^L_i})\) および状態 \((M^R_i,L_{M^R_i},R_{M^R_i})\) のみを遷移先の候補として考えれば十分です。（\(L_i=i\) または \(R_i=i\) のときは、それぞれ \(M^L_i\) または \(M^R_i\) が存在しないため候補から除かれ、特に \(L_i=R_i=i\) のときは \(dp[(i,L_i,R_i)]=0\) となります。）

ここで、\(i\) から（存在するならば） \(M^L_i\) および \(M^R_i\) に辺を張ったグラフを考えると、これは Cartesian Tree (Wikipedia) と呼ばれる二分木となっています（大小関係が通常の Cartesian Tree と逆であることに注意してください）。 よって、頂点 \(k_0\) を根とした Cartesian Tree を構成し、Cartesian Tree における、頂点 \(i\) の子を \(c^l_i,c^r_i\) として、\(dp[(i,L_i,R_i)]=\max( dp[(c^l_i,L_{c^l_i},R_{c^l_i})]+\lvert c^l_i-i\rvert, dp[(c^r_i,L_{c^r_i},R_{c^r_i})]+\lvert c^r_i-i\rvert )\) とした木DPを行うことによって答えを求められます。

Cartesian Tree の構成は stack 等のデータ構造を用いることで \(O(N)\) で行うことができ、木 DP も \(O(N)\) で行うことができるため、全体で \(O(N)\) でこの問題を解くことができ、本問題の制約下で十分高速です。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

const int N = 200000;
int n;
int a[N],lc[N],rc[N];

void make_tree(void){
	stack<int>st;
	for(int i=0;i<n;i++){
		while(!st.empty()){
			int x=st.top();
			if(a[x]>a[i])break;
			lc[i]=x;
			st.pop();
		}
		if(!st.empty())rc[st.top()]=i;
		st.push(i);
	}
	return;
}

long long dfs(int k){
	long long lcand=0,rcand=0;
	if(lc[k]>=0)lcand=dfs(lc[k])+(k-lc[k]); //abs(k-lc[k])=k-lc[k]
	if(rc[k]>=0)rcand=dfs(rc[k])+(rc[k]-k); //abs(k-rc[k])=rc[k]-k
	return max(lcand,rcand);
}

int main(void){
	int rt=-1;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		lc[i]=-1, rc[i]=-1;
		if(a[i]==n)rt=i;
	}
	make_tree();
	cout << dfs(rt) << endl;
	return 0;
}