Description

给定一个序列 $[a_1, a_2, \dots, a_n]$。要求计算满足条件的 $(l, r)$ 对的数量，其中 $1 \leq l \leq r \leq n$ 并且序列 $[a_l, a_{l+1}, \dots, a_r]$ 是双调序列。

Input Format

第一行输入一个整数 $n$（$1 \leq n \leq 300000$）。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$）。

Output Format

输出一个整数，即满足 $1 \leq l \leq r \leq n$ 且序列 $[a_l, a_{l+1}, \dots, a_r]$ 是双调序列的 $(l, r)$ 对的数量。

5
1 1 2 3 1

11

3
1 1 1

3

Hint

在样例一中，满足条件的 $(l, r)$ 对如下：

• $(1, 1)$，对应序列 $[1]$；
• $(2, 2)$，对应序列 $[1]$；
• $(2, 3)$，对应序列 $[1, 2]$；
• $(2, 4)$，对应序列 $[1, 2, 3]$；
• $(2, 5)$，对应序列 $[1, 2, 3, 1]$；
• $(3, 3)$，对应序列 $[2]$；
• $(3, 4)$，对应序列 $[2, 3]$；
• $(3, 5)$，对应序列 $[2, 3, 1]$；
• $(4, 4)$，对应序列 $[3]$；
• $(4, 5)$，对应序列 $[3, 1]$；
• $(5, 5)$，对应序列 $[1]$。

对于 $100\%$ 的数据，$1 \leq a_i \leq n \leq 300000$。