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