Олимпиадный тренинг

Задача . Битоническая последовательность


Задача

Темы: "Два указателя"

Последовательность \([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

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Python1
Комментарий учителя