/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
N 個のキャットタワーが左右一列に並んでおり、左から i 番目 (1\leq i\leq N) のタワーの高さは P_i です。
ここで、(P_1,P_2,\ldots,P_N) は (1,2,\ldots,N) の並び替えとなっています。
また、左から i 番目のタワーと j 番目のタワーの間の距離を \lvert i-j\rvert で定義します。
猫が一匹おり、最初、高さ N のキャットタワーの上にいます。
高橋君はタワーを一つ選んで撤去することを繰り返すことで、この猫を運動させたいです。
高橋君がタワーを撤去するとき、猫は以下のように移動します。
- 撤去するタワーの上に猫がいない場合、猫は移動しません。
- 撤去するタワーの上に猫がおり、かつそのタワーと左右に隣接するタワーのうち少なくとも一方が存在するとき、撤去されるタワーからスタートして隣接するタワーへの移動を繰り返して到達できるタワーのうち、撤去されるタワーを除いて最も高いタワーに猫が移動します。 このとき、移動前と移動後のタワーの間の距離だけ移動が発生します（移動前後および途中のタワーの高さは関係しません）。
- 撤去するタワーの上に猫がおり、かつそのタワーと左右に隣接するタワーが存在しないとき、猫は高橋君の腕の中に飛び込み、運動はここで終了となります。このときには移動は発生しません。
ここで、撤去したタワーの間は詰めることはありません。 すなわち、最初の時点で左から i 番目のタワーと隣接しているタワーは（存在すれば）左から (i-1) 番目と (i+1) 番目のタワーのみであり、 その後 他のタワーの撤去によって新しく他のタワーと隣接するようになることはありません。
運動が終了するまでの猫の移動距離の合計としてあり得る最大の値を求めてください。
制約
- 1\leq N\leq 2\times 10^5
- (P_1,P_2,\ldots, P_N) は (1,2,\ldots,N) の並び替えである。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \ldots P_N
出力
運動が終了するまでの猫の移動距離の合計としてあり得る最大の値を出力せよ。
入力例 1
5 5 3 4 1 2
出力例 1
5
最初、キャットタワーの高さは左から順に 5,3,4,1,2 です。
以下、左から i 番目 (1\leq i\leq 5) のキャットタワーをタワー i と呼びます。
最初、猫はタワー 1（高さ 5）にいます。
高橋君がタワー 1,2,3,5,4 の順に取り除くと猫は次のように移動します。
- 高橋君がタワー 1 を取り除く。タワー 1 から隣接するタワーへの移動のみで移動できるタワーは（タワー 1 を除いて）タワー 2,3,4,5 である。猫はこのうち最も高いタワー 3（高さ 4 ）に移動する。
- 高橋君がタワー 2 を取り除く。猫は移動しない。
- 高橋君がタワー 3 を取り除く。タワー 3 から隣接するタワーへの移動のみで移動できるタワーは（タワー 3 を除いて）タワー 4,5 である。猫はこのうち最も高いタワー 5（高さ 2 ）に移動する。
- 高橋君がタワー 5 を取り除く。タワー 5 から隣接するタワーへの移動のみで移動できるタワーは（タワー 5 を除いて）タワー 4 のみである。猫はタワー 4（高さ 1 ）に移動する。
- 高橋君がタワー 4 を取り除く。猫は高橋君の腕に飛び込み、運動は終了する。
このとき、猫の移動距離の合計は \lvert 1-3\rvert+\lvert 3-5\rvert+\lvert 5-4\rvert=5 となります。 移動距離の合計を 6 以上にする取り除き方は存在しないため、5 を出力します。
入力例 2
3 1 3 2
出力例 2
1
最初、キャットタワーの高さは左から順に 1,3,2 です。
以下、左から i 番目 (1\leq i\leq 3) のキャットタワーをタワー i と呼びます。
最初、猫はタワー 2（高さ 3）にいます。
高橋君がタワー 2,3 の順に取り除くと猫は次のように移動します。
- 高橋君がタワー 2 を取り除く。タワー 2 から隣接するタワーへの移動のみで移動できるタワーは（タワー 2 を除いて）タワー 1,3 である。猫はこのうち最も高いタワー 3（高さ 2 ）に移動する。
- 高橋君がタワー 3 を取り除く。猫は高橋君の腕に飛び込み、運動は終了する。
このとき、猫の移動距離の合計は \lvert 2-3\rvert=1 となり、このときが最大です。
タワー 2 を取り除いた後も、タワー 1 とタワー 3 は隣接しているとみなされないことに注意してください。
Score : 550 points
Problem Statement
There are N cat towers arranged in a row from left to right, and the height of the i-th tower from the left (1\leq i\leq N) is P_i.
Here, (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
The distance between the i-th tower and the j-th tower from the left is defined as \lvert i-j\rvert.
There is one cat, initially on top of the cat tower of height N.
Takahashi wants to exercise this cat by repeatedly choosing and removing towers.
When Takahashi removes a tower, the cat moves as follows:
- If the cat is not on top of the tower being removed, the cat does not move.
- If the cat is on top of the tower being removed and at least one of the towers adjacent to the left or right of that tower exists, the cat moves to the tallest tower (excluding the tower being removed) among the towers that can be reached by repeatedly moving to adjacent towers starting from the tower being removed. At this time, the cat moves the distance between the tower before movement and the tower after movement (the heights of the towers before, after, and during movement do not matter).
- If the cat is on top of the tower being removed and no towers adjacent to the left or right of that tower exist, the cat jumps into Takahashi's arms, and the exercise ends here. In this case, no movement occurs.
Here, the spaces between removed towers are not filled in. That is, the towers adjacent to the i-th tower from the left initially are only the (i-1)-th and (i+1)-th towers from the left (if they exist), and they will never become adjacent to other towers due to the removal of other towers afterward.
Find the maximum possible total distance the cat moves before the exercise ends.
Constraints
- 1\leq N\leq 2\times 10^5
- (P_1,P_2,\ldots, P_N) is a permutation of (1,2,\ldots,N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
Output the maximum possible total distance the cat moves before the exercise ends.
Sample Input 1
5 5 3 4 1 2
Sample Output 1
5
Initially, the heights of the cat towers are 5,3,4,1,2 from left to right.
Hereafter, the i-th cat tower from the left (1\leq i\leq 5) is called tower i.
Initially, the cat is on tower 1 (height 5).
If Takahashi removes towers in the order 1,2,3,5,4, the cat moves as follows:
- Takahashi removes tower 1. The towers that can be reached by only moving to adjacent towers from tower 1 are towers 2,3,4,5 (excluding tower 1). The cat moves to tower 3 (height 4), which is the tallest among them.
- Takahashi removes tower 2. The cat does not move.
- Takahashi removes tower 3. The towers that can be reached by only moving to adjacent towers from tower 3 are towers 4,5 (excluding tower 3). The cat moves to tower 5 (height 2), which is the tallest among them.
- Takahashi removes tower 5. The towers that can be reached by only moving to adjacent towers from tower 5 are only tower 4 (excluding tower 5). The cat moves to tower 4 (height 1).
- Takahashi removes tower 4. The cat jumps into Takahashi's arms, and the exercise ends.
Here, the cat moves the total distance of \lvert 1-3\rvert+\lvert 3-5\rvert+\lvert 5-4\rvert=5. There is no way to remove towers that makes the total distance moved 6 or more, so output 5.
Sample Input 2
3 1 3 2
Sample Output 2
1
Initially, the heights of the cat towers are 1,3,2 from left to right.
Hereafter, the i-th cat tower from the left (1\leq i\leq 3) is called tower i.
Initially, the cat is on tower 2 (height 3).
If Takahashi removes towers in the order 2,3, the cat moves as follows:
- Takahashi removes tower 2. The towers that can be reached by only moving to adjacent towers from tower 2 are towers 1,3 (excluding tower 2). The cat moves to tower 3 (height 2), which is the tallest among them.
- Takahashi removes tower 3. The cat jumps into Takahashi's arms, and the exercise ends.
Here, the cat moves the total distance of \lvert 2-3\rvert=1, which is the maximum.
Note that after removing tower 2, tower 1 and tower 3 are not considered to be adjacent.