The implementation is explained in the last two paragraph. If you understand that the problem can be boiled down to a Dynamic Programming (DP) on a binary tree, please refer to them.

Consider solving this problem with Dynamic Programming. Define the state \((i,l,r)\) where the cat is on tower \(i\) \((1\leq i\leq N)\), and the towers reachable by moving to adjacent towers are towers \(l,l+1,\ldots,r\) \((1\leq l\leq i\leq r\leq N)\). The maximum possible total travel distance from state \((i,l,r)\) until the exercise ends is unique regardless of the past moves; denote this value by \(dp[(i,l,r)]\).
The sought answer is \(dp[(k_0,1,N)]\), where \(k_0\) is the tower of height \(N\).

Here, any state \((i,l,r)\) reachable (possibly transitively) from the initial state \((k_0,1,N)\) must satisfy:

• \(P_l,P_{l+1},\ldots, P_r\) are all \(P_i\) or less.

This is because the cat is initially on the highest (height-\(N\)) tower and, by definition of its moves, it always holds during the process of removing towers that when the cat is on tower \(k\), any tower reachable by moving to adjacent towers has a height \(k\) or less.

Here, for \(1\leq k\leq N\), define \([L_k,R_k]\) as the maximal interval such that \(1\leq L_k\leq k \leq R_k\leq N\) and “if \(L_k\leq i\leq R_k\) then \(P_i\leq P_k\).” In other words,

• If there exists \(i\) with \(i<k\) and \(P_i>P_k\), then \(L_k=i+1\) for the maximum such \(i\); otherwise, \(L_k=1\).
• If there exists \(j\) with \(k<j\) and \(P_j>P_k\), then \(R_k=j-1\) for the minimum such \(j\); otherwise, \(R_k=N\).

By the prior observation, it is sufficient to consider the states \((i,l,r)\) with \(L_i\leq l\leq i\leq r\leq R_i\).
Moreover, notice that any state \((i,l,r)\) is transitionable from state \((i,L_i,R_i)\) (because we may remove towers \(l-1\) and \(r+1\) as needed). Thus, \(dp[(i,L_i,R_i)]\geq dp[(i,l,r)]\).

Next, we will prove the following fact:

If there exists \((l,r)\) \((L_i\leq l\leq i\leq r\leq R_i)\) such that removing tower \(i\) from state \((i,l,r)\) leads (directly) to state \((j,l',r')\), then one can turn state \((i,L_i,R_i)\) into state \((j,L_j,R_j)\) by appropriately performing operations.

The former transition is possible if and only if \(L_i\leq j\leq R_i\) and there is no tower with height \(P_j\) or taller from tower \(j\) through tower \(i\) (that is, towers \(j,j+1,\ldots,i\) or \(i,i+1,\ldots,j\))—otherwise, it is impossible to move from tower \(i\) to tower \(j\) by removing tower \(i\). Conversely, if this criteria holds, we claim that the latter transition is always possible. By symmetry, it is sufficient to construct an operation sequence for cases where \(j<i\): indeed, we may remove tower \(L_j-1\) (if \(L_i<L_j\)) and tower \(i+1\) (if \(i<R_i\)) and then remove tower \(R_j+1\) (note that \(R_j+1=i\) by assumption).

Here, the transition \((i,L_i,R_i)\to (i,l,r)\to (j,l',r')\) incurs a maximum total travel distance of \( dp[(j,l',r')]+\lvert i-j\rvert\), while the transition \((i,L_i,R_i)\to (j,L_j,R_j)\) incurs \( dp[(j,L_j,R_j)]+\lvert i-j\rvert\). Since the latter is always larger, it is sufficient to consider transitions of the latter form; particularly, take into account states \((i,L_i,R_i)\).

Moreover, if we define \(M^L_i\) as the tallest tower among towers \(L_i,L_i+1,\ldots, i-1\), and \(M^R_i\) as the tallest among \(i+1, i+2,\ldots, R_i\), we have the following fact

if state \((i,L_i,R_i)\) is transitionable from state \((j,L_j,R_j)\), the state is transitionable from \((M^L_i,L_{M^L_i},R_{M^L_i})\) if \(j<i\), and transitionable from \((M^R_i,L_{M^R_i},R_{M^R_i})\) if \(i<j\).

By symmetry, it is sufficient to show that the state is transitionable from \((M^L_i,L_{M^L_i},R_{M^L_i})\) if \(j<i\). Actually it can be asserted by the following three properties:

• \(L_{M^L_i}\leq j\leq R_{M^L_i}\) holds.
• For any \(i'\) and \(L_{i'}\leq j'\leq R_{i'}\), there exists \((l,r)\) such that state \((j',L_{j'},R_{j'})\) is reachable from state \((i',L_{i'},R_{i'})\).
• If there exist \(l,r,l',r'\) such that state \((j',l',r')\) is reachable from \((i',l,r)\), then state \((j',L_{j'},R_{j'})\) is reachable from \((i',L_{i'},R_{i'})\).

The first bullet point follows from the definition. For the second, it is achievable by repeatedly removing all towers in the cat’s side not containing tower \(j'\) and then removing the current tower. The third can be confirmed by repeatedly applying the discussion for the direct transition mentioned above.

By the fact shown, it is sufficient to consider the transitions from state \((i,L_i,R_i)\) to states \((M^L_i,L_{M^L_i},R_{M^L_i})\) and \((M^R_i,L_{M^R_i},R_{M^R_i})\). (If \(L_i=i\) or \(R_i=i\), then \(M^L_i\) or \(M^R_i\) is undefined, respectively, so we ignore the corresponding destinations; in particular, if \(L_i=R_i=i\), then \(dp[(i,L_i,R_i)]=0\).)

Here, if you consider graph where there are edges from \(i\) to \(M^L_i\) and \(M^R_i\) (if present), this graph forms a binary tree called Cartesian Tree. (Note that the ordering is reversed compared to an ordinary Cartesian Tree.) Therefore, the problem can be solved by constructing a Cartesian Tree rooted at vertex \(k_0\), and performing a tree DP with \(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 )\). where \(c^l_i\) and \(c^r_i\) are the children of vertex \(i\).

The Cartesian Tree can be constructed using a data structure like a stack in \(O(N)\) time, and the tree DP can also be done in \(O(N)\) time, so the problem can be solved in a total of \(O(N)\) time, which is fast enough under the constraints of the problem statement.

Sample code 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;
}