В жизни всё время чередуются взлёты и падения, прямо как в забавных последовательностях. Последовательность 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, то последовательность станет забавной.
Примечание
В первом примере получить забавную последовательность можно двумя способами:
- Поменять местами t2 = 8 и t4 = 7.
- Поменять местами t1 = 2 и t5 = 7.
Во втором примере есть только один способ получить забавную последовательность: поменять местами t1 = 200 и t4 = 50.