题目描述

小 Y 的朋友小 W 带她去神庙考古。

这座神庙中有 $n$ 座排成一排的高塔，相邻两座塔的距离为 $1$，从左往右的第 $i$ 座塔的高度为 $h_i$，并且没有两座塔的高度相同。

小 Y 开始观察这些高塔，她认为第 $i$ 座塔的宽度是所有高度超过 $h_i$ 的塔中，与第 $i$ 座塔距离的最小值，即 $\min\{|i-j|:h_j>h_i\}$，如果不存在这样的塔，则定义宽度为 $0$。

现在小 Y 想知道 $n$ 座塔的宽度总和，但是她不想自己计算，所以请你告诉她答案。

输入格式

从文件 temple.in 中读入数据。

第一行一个整数 $n$，表示塔的数量。

第二行 $n$ 个整数，第 $i$ 个表示从左往右第 $i$ 座塔的高度 $h_i$。

输出格式

输出到文件 temple.out 中。

输出一行一个整数，表示 $n$ 座塔的宽度总和。

样例 1 输入

5
5 8 1 6 7

样例 1 输出

6

样例 1 解释

五座塔的宽度分别为 $1,0,1,1,3$。

样例 2

见选手目录下的 temple/temple2.in 与 temple/temple2.ans。

该样例满足子任务 $1$ 的约束条件。

样例 3

见选手目录下的 temple/temple3.in 与 temple/temple3.ans。

该样例满足子任务 $2$ 的约束条件。

样例 4

见选手目录下的 temple/temple4.in 与 temple/temple4.ans。

该样例满足子任务 $3$ 的约束条件。

样例 5

见选手目录下的 temple/temple5.in 与 temple/temple5.ans。

该样例满足子任务 $4$ 的约束条件。

样例 6

见选手目录下的 temple/temple6.in 与 temple/temple6.ans。

该样例满足子任务 $5$ 的约束条件。

数据范围

对于所有测试数据，保证 $1\le n\le 2\times 10^5,1\le h_i\le 10^9$，且 $h_1,h_2,\dots,h_n$ 两两不同。

特殊性质 A：对于所有 $1\le i\le n-1$，满足 $h_i<h_{i+1}$。 特殊性质 B：$(h_1,h_2,\dots,h_n)$ 在 $(1,2,\dots,n)$ 的所有排列中等概率随机选择一个。 特殊性质 C：对于所有 $1\le i\le n$，满足 $h_i\le n$。

本题开启所有合理的子任务依赖。