The life goes up and down, just like nice sequences. Sequence t₁,t₂,...,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₁,t₂,...,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₁,t₂,...,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.