A10293. Bear and Up-Down

The life goes up and down, just like nice sequences. Sequence $t_{1},t_{2},...,t_{n}$ is called nice if the following two conditions are satisfied:

- $t_{i}<t_{i+1}$ for each odd $i<n$ ;
- $t_{i}>t_{i+1}$ for each even $i<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 $t_{1},t_{2},...,t_{n}$ . This sequence is not nice now and Limak wants to fix it by a single swap. He is going to choose two indices $i<j$ and swap elements $t_{i}$ and $t_{j}$ 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<=n<=150000$ ) — the length of the sequence.

The second line contains $n$ integers $t_{1},t_{2},...,t_{n}$ ( $1<=t_{i}<=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:

1. Swap $t_{2}=8$ with $t_{4}=7$ .
2. Swap $t_{1}=2$ with $t_{5}=7$ .

In the second sample, there is only one way — Limak should swap $t_{1}=200$ with $t_{4}=50$ .