题目背景

测绘队沿一条山脊布了一排测点。看一段剖面时，如果最高的那座峰恰好落在剖面的两端之一，这一段剖面就被认为视野通透。

题目描述

山脊上有 $n$ 座山峰排成一列，第 $i$ 座山峰的高度为 $a_i$。

对于一对下标 $l \le r$，把山峰 $l, l+1, \dots, r$ 称作一个区间。如果这个区间内高度的最大值恰好等于 $a_l$ 或者恰好等于 $a_r$，就称这个区间是开阔的（最高峰坐落在区间两端的其中一端上）。

请你统计有多少个区间是开阔的。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

输出一行一个整数，表示开阔区间的个数。

输入输出样例 #1

输入 #1

3
1 2 3

输出 #1

6

输入输出样例 #2

输入 #2

2
1 1

输出 #2

3

输入输出样例 #3

输入 #3

5
2 5 3 5 1

输出 #3

12

说明

样例解释

样例 1 中高度严格递增，任何区间的最大值都在右端点上，因此 $3$ 座山峰给出的 $\frac{3 \times 4}{2} = 6$ 个区间全部开阔。

样例 2 中有 $3$ 个区间：$[1,1]$、$[2,2]$ 各只有一个山峰，最高峰自然在端点上；$[1,2]$ 两座山峰一样高，最大值也等于端点上的取值。所以答案为 $3$。

数据范围

• 对于 $30\%$ 的数据，$n \le 300$；
• 对于 $60\%$ 的数据，$n \le 3000$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le a_i \le 10^9$。