Fill的序列

Fill喜欢这样的序列：

对于第i个数(i<n)，如果i为奇数，则a[i]<a[i+1]，否则a[i]>a[i+1]，只要有一个数不满足这个条件Fill就会讨厌这个序列

给定一个Fill讨厌的序列，你只能交换其中的两个数，请问有多少种交换方案可以得到Fill喜欢的序列

第一行输入一个整数n（2<=n<=150000）代表序列的长度

第二行输入n个整数a1,a2,……,an(1<=ti<=150000)，表示这个序列

输出一个整数代表有多少种方案交换两个整数后能得到Fill喜欢的序列

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

 Note

对于第一组样例，有两种交换方案 
 
 
 交换t2 = 8 和t4 = 7. 
 
 交换t1 = 2 和t5 = 7. 

对于第二组样例，只有一种方案 — 交换 t1 = 200 和t4 = 50.