AT_abc435_f [ABC435F] Cat exercise

有 $N$ 个猫塔从左到右排列成一排，第 $i$ 个猫塔（$1\leq i\leq N$）的高度为 $P_i$。 这里，$(P_1,P_2,\ldots,P_N)$ 是 $(1,2,\ldots,N)$ 的一个排列。 第 $i$ 个猫塔和第 $j$ 个猫塔之间的距离定义为 $|i-j|$。 有一只猫，最初在高度为 $N$ 的猫塔顶上。 高桥想让这只猫锻炼身体，于是反复选择并移除一些猫塔。 当高桥移除一个猫塔时，猫的动作如下： - 如果猫不在被移除的猫塔上，猫不会移动。 - 如果猫在被移除的猫塔上，并且该塔的左或右相邻猫塔至少有一个仍然存在，则猫会移动到（从被移除塔开始，仅可以通过相邻走到达的）所有当前连通的猫塔中高度最高的那个塔（不包括被移除的塔）。此时，猫会移动的距离等于移动前后的塔的编号之差的绝对值（与塔的高度无关）。 - 如果猫在被移除的猫塔上，并且该塔没有相邻塔存在，则猫会直接跳进高桥的怀里，锻炼就此结束。在这种情况下猫不会移动。 这里，被移除猫塔后，其间的空隙不会被填补。也就是说，初始时左数第 $i$ 个猫塔的相邻塔只有第 $i-1$ 个和第 $i+1$ 个（若存在），并且移除其它猫塔后这些相邻关系不会改变，永远不会由于其它猫塔被移除而成为新的相邻关系。 请你求出在锻炼结束前，猫最多能走的总距离是多少。

输入从标准输入获得，格式如下： > $N$ $P_1$ $P_2$ $\cdots$ $P_N$

输出猫在锻炼结束前最多能走的总距离。

## 样例解释 1 初始时猫塔的高度从左到右分别为 $5,3,4,1,2$。 下面称左数第 $i$ 个猫塔为第 $i$ 号塔（$1\leq i\leq 5$）。 起始时，猫在第 $1$ 号塔（高度 $5$）上。 如果高桥按顺序移除 $1,2,3,5,4$ 号塔，则猫的移动如下： - 第一次移除塔 $1$，可以通过相邻连接（不经过 $1$ 号塔）到达的塔有 $2,3,4,5$，其中最高的是 $3$ 号塔（高度 $4$），猫移动到塔 $3$。猫走的距离为 $|1-3|=2$。 - 移除塔 $2$，猫不在其上，不移动。 - 移除塔 $3$，可以通过相邻把猫带到 $4$ 号或 $5$ 号塔（不包括 $3$ 号）。其中，$5$ 号塔高度 $2$，高于 $4$ 号塔。猫移动到 $5$ 号塔，距离为 $|3-5|=2$。 - 移除塔 $5$，猫被带到 $4$ 号塔，距离 $|5-4|=1$。 - 移除塔 $4$，猫已到尽头，跳进高桥怀里，锻炼结束。 最终，猫总共移动了 $2+2+1=5$，不存在移动距离超过 $5$ 的方案，因此输出 $5$。 ## 样例解释 2 初始时猫塔的高度从左到右为 $1,3,2$。 左数第 $i$ 个塔记为第 $i$ 号塔。 猫初始在第 $2$ 号塔（高度 $3$）。 若高桥移除 $2,3$ 号塔，猫的移动如下： - 移除塔 $2$，剩下塔 $1$ 和塔 $3$。猫会去最高的 $3$ 号塔，上下移动距离为 $|2-3|=1$。 - 移除塔 $3$，猫直接跳进高桥怀里。 此时，猫移动的总距离为 $1$，且这是最大值。 注意，移除 $2$ 号塔后，$1$ 号和 $3$ 号塔并不因为 $2$ 号塔被移除而变为相邻。 ## 数据范围 - $1\leq N\leq 2\times 10^5$ - $(P_1,P_2,\ldots, P_N)$ 是 $(1,2,\ldots,N)$ 的一个排列。 - 所有输入均为整数。 由 ChatGPT 5 翻译