P15150 [SWERC 2024] Temple Architecture

你正在挖掘一座非常古老的印度寺庙的遗迹。这座寺庙的建筑结构十分奇特：你发现了一排 $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}$，以空格分隔。

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

#### 样例解释 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 完成