C. Медвежонок, взлёты и падения
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В жизни всё время чередуются взлёты и падения, прямо как в забавных последовательностях. Последовательность t1, t2, ..., tn называется забавной, если выполнены следующие два условия:

  • ti < ti + 1 для всех нечётных i < n;
  • ti > ti + 1 для всех чётных i < n.

Например, последовательности (2, 8), (1, 5, 1) и (2, 5, 1, 100, 99, 120) являются забавными, а (1, 1), (1, 2, 3) и (2, 5, 3, 2) нет.

У полярного медвежонка Лимака есть последовательность целых положительных чисел t1, t2, ..., tn. Это последовательность не является забавной, и Лимак хочет это исправить. Он ровно один раз выберет какие-то два элемента и поменяет их местами. Посчитайте число таких пар индексов i < j, что если поменять местами соответствующие элементы ti и tj, то последовательность станет забавной.

Входные данные

В первой строке входных данных записано число n (2 ≤ n ≤ 150 000) — длина последовательности t.

Во второй строке записаны n целых чисел t1, t2, ..., tn (1 ≤ ti ≤ 150 000) — исходная последовательность. Гарантируется, что она не является забавной.

Выходные данные

Выведите количество способов поменять два элемента ровно один раз, чтобы сделать имеющуюся последовательность забавной.

Примеры
Входные данные
5
2 8 4 7 7
Выходные данные
2
Входные данные
4
200 150 100 50
Выходные данные
1
Входные данные
10
3 2 1 4 1 4 1 4 1 4
Выходные данные
8
Входные данные
9
1 2 3 4 5 6 7 8 9
Выходные данные
0
Примечание

В первом примере получить забавную последовательность можно двумя способами:

  1. Поменять местами t2 = 8 и t4 = 7.
  2. Поменять местами t1 = 2 и t5 = 7.

Во втором примере есть только один способ получить забавную последовательность: поменять местами t1 = 200 и t4 = 50.