The life goes up and down, just like nice sequences. Sequence t1,t2,...,tn is called nice if the following two conditions are satisfied:
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.
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.
Print the number of ways to swap two elements exactly once in order to get a nice sequence.
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
In the first sample, there are two ways to get a nice sequence with one swap:
In the second sample, there is only one way− Limak should swap t1=200 with t4=50.