← 返回题目列表

AtCoder · abc435_f

I. 猫运动

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

有 N 猫塔从左到右排列成一排,塔的高度 i左起第 塔 (1\leq i\leq N) is P_i.
在这里, (P_1,P_2,\ldots,P_N) 是一个排列 (1,2,\ldots,N).
之间的距离 i第塔和 j左边第一个塔定义为 \lvert i-j\rvert.

有一只猫,最初在猫塔高度 N.
高桥想通过反复选择和移除塔来锻炼这只猫。

当高桥拆除塔时,猫的移动方式如下:

  • 如果猫不在被移除的塔顶,则猫不会移动。
  • 如果猫位于被移除塔的顶部,并且该塔左侧或右侧至少存在一个相邻的塔,则猫会移动到从被移除塔开始反复移动到相邻塔可到达的塔中最高的塔(不包括被移除塔)。 此时,猫移动移动前的塔和移动后的塔之间的距离(移动前、移动后和移动期间塔的高度无关紧要)。
  • 如果猫位于被移除的塔的顶部,并且该塔左侧或右侧不存在相邻的塔,则猫跳入高桥的怀里,练习到此结束。在这种情况下,不会发生任何运动。

这里,移除的塔之间的空间没有被填充。 也就是说,毗邻的塔楼 i从左边开始第一个塔只是 (i-1)-th 和 (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 是塔 2,3,4,5 (不包括塔 1)。猫移动到塔楼 3 (高度 4),这是其中最高的。
  • 高桥拆除塔 2。猫一动不动。
  • 高桥拆除塔 3。仅从塔楼移动到相邻塔楼即可到达的塔楼 3 是塔 4,5 (不包括塔 3)。猫移动到塔楼 5 (高度 2),这是其中最高的。
  • 高桥拆除塔 5。仅从塔楼移动到相邻塔楼即可到达的塔楼 5 仅有塔 4 (不包括塔 5)。猫移动到塔楼 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 是塔 1,3 (不包括塔 2)。猫移动到塔楼 3 (高度 2),这是其中最高的。
  • 高桥拆除塔 3。猫跳进高桥的怀里,练习结束。

这里,猫移动的总距离为 \lvert 2-3\rvert=1,这是最大值。
请注意,拆除塔后 2,塔 1 和塔 3 不被视为相邻。