跳至正文
题库1622
#1622

Bear and Up-Down

查看题目操作

Bear and Up-Down

题目描述

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<ti+1 for each odd i<n;
  • ti>ti+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 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<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.

Input

The first line of the input contains one integer n (2≤n≤150000)− the length of the sequence.

The second line contains n integers t1,t2,...,tn (1≤ti≤150000) − 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.

Examples

5
2 8 4 7 7
2
4
200 150 100 50
1
10
3 2 1 4 1 4 1 4 1 4
8
9
1 2 3 4 5 6 7 8 9
0

Note

In the first sample, there are two ways to get a nice sequence with one swap:

  1. Swap t2=8 with t4=7.
  2. Swap t1=2 with t5=7.

In the second sample, there is only one way− Limak should swap t1=200 with t4=50.