题目描述

译自 ROI Regional 2024 Day1 T2. Битоническая последовательность

如果序列 $[b_1, b_2, \ldots, b_k]$ 满足对某个 $1 \le i \le k$，$b_1 < b_2 < \ldots < b_i > \ldots > b_k$，则称该序列为双调序列。

例如，序列 $[1]$，$[1, 2, 3, 2]$，$[1, 4, 10]$，$[3, 2]$ 是双调序列，而序列 $[1, 1]$，$[2, 1, 3]$ 不是双调序列。

给定一个序列 $[a_1, a_2, \ldots, a_n]$。需要计算满足 $1 \le l \le r \le n$ 且子序列 $[a_l, a_{l+1}, \ldots, a_r]$ 是双调序列的 $(l, r)$ 对的数量。

输入格式

第一行输入包含一个整数 $n$ $(1 \leq n \leq 3\cdot 10^5)$。

第二行输入包含 $n$ 个整数：$a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq n)$。

输出格式

输出一个整数，表示满足条件的 $(l, r)$ 对的数量。

样例

样例 1

输入

5
1 1 2 3 1

输出

11

解释：满足条件的 $(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]$

样例 2

输入

3
1 1 1

输出

3

数据范围与提示

详细子任务附加限制及分值如下表所示。