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.