P11121 [ROIR 2024] 双调序列 (Day 1)

翻译自 [ROIR 2024 D1T2](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-regional-2024-day1.pdf)。 称一个序列 $[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)$ 对的数量。

在样例一中，满足条件的 $(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]$。 | 子任务 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $0$ | $0$ | 同样例 | | $1$ | $27$ | $n\le500$ | | $2$ | $14$ | $n\le5000$ | | $3$ | $20$ | 所有 $a_i$ 互不相等 | | $4$ | $39$ | 无 | 对于 $100\%$ 的数据，$1 \leq a_i \leq n \leq 300000$。