生活起起落落,就像精彩的序列一样。如果满足以下两个条件,则序列 t1, t2, ..., tn 被称为“nice”:
- 对于每个奇数 i < n,ti < ti + 1;
- 对于每个偶数 i < n,ti > ti + 1。
例如,序列 (2, 8)、(1, 5, 1) 和 (2, 5, 1, 100, 99, 120) 很好,而 (1, 1)、(1, 2, 3) 和 (2, 5, 3, 2) 则不好。
Bear Limak 有一个正整数序列 t1, t2, ..., tn。这个序列现在不太好,Limak 希望通过一次交换来修复它。他将选择两个索引 i < j 并交换元素 ti 和 tj 以获得一个好的序列。数一下有多少种方法可以做到这一点。如果为交换选择的元素索引不同,则两种方式被认为是不同的。
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 150 000) - 序列的长度。
第二行包含 n 个整数 t1, t2, ..., tn (1 ≤ ti ≤ 150 000) — 初始序列。保证给定的序列不好。
输出
打印一次交换两个元素以获得良好序列的方法数。
示例
输入 #1
5 2 8 4 7 7
输出 #1
2
输入 #2
4 200 150 100 50
输出 #2
1
输入 #3
10 3 2 1 4 1 4 1 4 1 4
输出 #3
8
输入#4
9 1 2 3 4 5 6 7 8 9
输出#4
0
注意
在第一个示例中,有两种方法可以通过一次交换获得良好的序列:
1. 将 t2 = 8 与 t4 = 7 交换。
2. 将 t1 = 2 与 t5 = 7 交换。
在第二个示例中,只有一种方法 — Limak 应该将 t1 = 200 替换为 t4 = 50。