说明

你正在挖掘一座非常古老的印度寺庙的遗迹。这座寺庙的建筑结构十分奇特：你发现了一排 $N$ 座高度各不相同的塔（没有两座塔高度相同），它们彼此间隔一米（每座塔的半径可忽略不计）。

在挖掘过程中，你发现了一些可能解释这种奇特建筑结构的东西：建筑师的坟墓。你在坟墓上发现了以下墓志铭：

哦，汝寺庙建造者，
欲臻完美，须造访每座塔；
对每一座，计算其至更高之最近塔¹的距离；
将所有这些距离相加。
若汝能遵循此指引，
由此结果汝将得启迪，
汝之寺庙香火必鼎盛。

¹ 更高的最近塔可能在左侧或右侧。对于最高的塔，此距离未定义，不应计入最终总和。

你想知道如何计算这个总和，即寺庙的“启蒙分数”。

给定一个正整数 $N$ 对应于塔的数量，以及一个由 $N$ 个互不相同的非负整数组成的数组 $H$ 对应于塔的高度。$H_0$ 是最左侧塔的高度，$H_1$ 是 $H_0$ 右侧塔的高度，依此类推。最后，$H_{N-1}$ 是最右侧塔的高度。注意，任意两座塔之间的距离（以米为单位）是它们在数组 $H$ 中索引之差的绝对值。令 $p$ 表示 $H$ 中最高塔的索引，并对每个 $i \neq p$ 定义

$$d(i) = \min \{ |i - j| : \text{对于所有满足 } H_j > H_i \text{ 的 } j \}。$$

注意 $d(p)$ 未定义。寺庙的“启蒙分数”由下式给出：

$$\sum_{i=0, i \neq p}^{N-1} d(i)。$$

输入格式

第一行包含整数 $N$。第二行包含高度数组 $H$ 的元素 $H_0, \ldots, H_{N-1}$，以空格分隔。

输出格式

输出应包含一行，即寺庙的启蒙分数。

5
7 3 2 100 1

6

8
45 13 18 10 8 56 17 19

13

提示

样例解释 1

• 第 1 座塔至更高的最近塔（第 4 座塔）的距离：$3$
• 第 2 座塔至更高的最近塔（第 1 座塔）的距离：$1$
• 第 3 座塔至更高的最近塔（第 2 座或第 4 座塔）的距离：$1$
• 第 5 座塔至更高的最近塔（第 4 座塔）的距离：$1$

最高的塔（第 4 座）不计入。因此，$3+1+1+1=6$。

样例解释 2

• 第 1 座塔至更高的最近塔（第 6 座塔）的距离：$5$
• 第 2 座塔至更高的最近塔（第 1 座或第 3 座塔）的距离：$1$
• 第 3 座塔至更高的最近塔（第 1 座塔）的距离：$2$
• 第 4 座塔至更高的最近塔（第 3 座塔）的距离：$1$
• 第 5 座塔至更高的最近塔（第 4 座或第 6 座塔）的距离：$1$
• 第 7 座塔至更高的最近塔（第 6 座或第 8 座塔）的距离：$1$
• 第 8 座塔至更高的最近塔（第 6 座塔）的距离：$2$

最高的塔（第 6 座）不计入。因此，$5+1+2+1+1+1+2=13$。

数据范围

• $3 \leq N \leq 200000$；
• 对于 $i = 1, \ldots, N$，$1 \leq H_i \leq 10^{18}$；

翻译由 DeepSeek 完成