两端见证

题目描述

给定 $1,2,\dots,n$ 的一个排列 $a_1,a_2,\dots,a_n$。

称子数组 $a_l,a_{l+1},\dots,a_r$ 是一次「两端见证」，当且仅当这两个端点恰好分别是该子数组的最小值与最大值（顺序不限：左端可为最小、右端为最大，或相反）。长度为 $1$ 的子数组也算作合法见证。

请统计有多少个子数组是两端见证。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个互不相同的整数 $a_1,a_2,\dots,a_n$，构成 $1 \sim n$ 的排列。

输出格式

输出一行一个整数，表示两端见证的子数组个数。

样例

3
1 3 2

5

4
4 1 3 2

7

数据范围与提示

• $1 \le n \le 2 \times 10^5$。
• 样例 1 中，除整个数组 $[1,3,2]$ 外，其余 $5$ 个子数组都是两端见证。
• 样例 2 中共有 $7$ 个合法子数组。
• 答案可能超过 $32$ 位整数范围。