Последовательность \([b_1, b_2, \ldots, b_k]\) называется битонической, если выполнены неравенства \(b_1 < b_2 < \ldots < b_i > \ldots > b_k\) для некоторого \(1 \le i \le k\).
Например, последовательности \([1]\), \([1, 2, 3, 2]\), \([1, 4, 10]\), \([3, 2]\) являются битоническими, а последовательности \([1, 1]\), \([2, 1, 3]\) — нет.
Задана последовательность \([a_1, a_2, \ldots, a_n]\). Требуется количество пар \((l, r)\) таких, что \(1 \le l \le r \le n\) и последовательность \([a_l, a_{l+1}, \ldots, a_r]\) является битонической.
Формат входных данных
Первая строка ввода содержит число \(n\) (\(1 \leq n \leq 300\,000\)).
Вторая строка ввода содержит \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)).
Формат выходных данных
Выведите одно число — количество пар \((l, r)\), таких, что \(1 \le l \le r \le n\) и последовательность \([a_l, a_{l+1}, \ldots, a_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]\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 1 2 3 1
|
11
|
|
2
|
3
1 1 1
|
3
|