The life goes up and down, just like nice sequences. Sequence t1,t2,...,tn is called nice if the following two conditions are satisfied:
ti \lt ti+1 for each odd i \lt n; ti \gt ti+1 for each even i \lt n.
For example, sequences (2,8), (1,5,1) and (2,5,1,100,99,120) are nice, while (1,1), (1,2,3) and (2,5,3,2) are not.

Bear Limak has a sequence of positive integers t1,t2,...,tn. This sequence is not nice now and Limak wants to fix it by a single swap. He is going to choose two indices i \lt j and swap elements ti and tj in order to get a nice sequence. Count the number of ways to do so. Two ways are considered different if indices of elements chosen for a swap are different.

The first line of the input contains one integer n (2 \le n \le 150000)- the length of the sequence.

The second line contains n integers t1,t2,...,tn (1 \le ti \le 150000) - the initial sequence. It's guaranteed that the given sequence is not nice.

Print the number of ways to swap two elements exactly once in order to get a nice sequence.

In the first sample, there are two ways to get a nice sequence with one swap:
Swap t2=8 with t4=7. Swap t1=2 with t5=7.
In the second sample, there is only one way- Limak should swap t1=200 with t4=50.