猫咪锻炼

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

有 $N$ 座猫塔从左到右排成一行，第 $i$ 座塔的高度为 $P_i$，其中 $(P_1,P_2,\ldots,P_N)$ 是 $(1,2,\ldots,N)$ 的一个排列。两座塔 $i,j$ 之间的距离为 $|i-j|$。

猫最初位于高度为 $N$ 的塔顶。高桥会反复选择并移除一座尚未移除的塔。

• 若猫不在被移除的塔上，猫不移动。
• 若猫在被移除的塔上，且该塔左侧或右侧至少有一座仍存在的相邻塔，猫会移动到从该位置沿尚存相邻塔能够到达的所有塔中高度最高的一座，移动距离为两座塔编号之差的绝对值。
• 若猫所在的塔被移除时左右相邻塔均不存在，猫跳进高桥怀中，锻炼结束，且此次不产生移动距离。

移除塔后留下的空缺不会被填补，原本不相邻的塔不会成为新的相邻塔。

求在锻炼结束前，猫可能移动的最大总距离。

输入格式

第一行包含整数 $N$。

第二行包含 $N$ 个整数 $P_1,P_2,\ldots,P_N$。

输出格式

输出一个整数，表示最大总移动距离。

样例输入 1

5
5 3 4 1 2

样例输出 1

5

样例输入 2

3
1 3 2

样例输出 2

1

数据范围

• $1\le N\le 2\times 10^5$；
• $(P_1,P_2,\ldots,P_N)$ 是 $(1,2,\ldots,N)$ 的一个排列；
• 所有输入均为整数。

样例解释

第一组样例中，一种最优移除顺序是 $1,2,3,5,4$，猫依次移动 $2,2,1$，总距离为 $5$。