Problem D. Disordered polygon ≡

Author:Антон Карабанов, И. Блинов, А. Баранов   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

Zhenya drew a regular n-gon on the board, labeled its vertices with numbers clockwise in ascending order: "1 2 3 ... n". Nikita came up and rearranged the numbers in the signature, erased all sides of Zhenya's figure and connected the vertices in the resulting new order (including the first and last vertices). Now a closed broken line flaunts on the board. How many pairs of line segments intersect?

Input format

The first line of the input contains single integer n. The second line contains n numbers a1, a2… an — a permutation of the polygon's vertices.

Output format

Output a single non-negative integer — the answer to the problem question.

Constraints

3 ≤ n ≤ 105

Note on samples

Sample tests

No. Standard input Standard output
1 
4
1 2 3 4
 
0
2 
4
1 2 4 3
 
1
3 
5
2 4 5 3 1
 
2
4 
8
5 6 1 3 4 7 8 2
 
8
0.165s 0.038s 15