题目背景

翻译自 ROIR 2024 D1T2。

称一个序列 $[b_1, b_2, \dots, b_k]$ 为双调序列（Bitonic Sequence），当且仅当存在一个 $1 \leq i \leq k$ 使得 $b_1 < b_2 < \dots < b_i > \dots > b_k$。

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

题目描述

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

输入格式

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

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

输出格式

输出一个整数，即满足 $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

提示

在样例一中，满足条件的 $(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$。