部落信号

时间限制：2 秒 / 内存限制：256 MB

Description

给定 $n$ 个数 $a_1, a_2, \dots, a_n$，这些数围成一个环，两个数能看到当且仅当两条路径中一条满足所有数都小于等于这两个数。

请问有多少对数能互相看见。

Input

• 输入的第一行是一个整数 $n$ ($3 \leq n \leq 10^6$)，表示数的个数。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，这些整数的值范围是 $[1, 10^9]$。

Output

• 输出答案。

Example

Sample Input

5 
1 2 4 5 3

Sample Output

7