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.

Input

The first line of the input contains one integer $*n*$ ($2 ≤ *n* ≤ 150 000$) — the length of the sequence.

The second line contains $*n*$ integers $*t*_{1}, *t*_{2}, ..., *t*_{*n*}$ ($1 ≤ *t*_{*i*} ≤ 150 000$) — the initial sequence. It's guaranteed that the given sequence is not nice.

Output

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

Note

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$.