Задача №115215. Битоническая последовательность
Последовательность \([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 | 27 | \(n \le 500\) | первая ошибка | |
| 2 | 14 | \(n \le 5000\) | 1 | первая ошибка |
| 3 | 20 | все числа \(a_i\) различны | первая ошибка | |
| 4 | 39 | — | 1–3 | первая ошибка |
В первом примере подходят следующие пары:
- \((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]\)
5 1 1 2 3 1
11
3 1 1 1
3