## Problem D. Disordered polygon ≡

• problems
• en ru
 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.

3 ≤ n ≤ 105

### 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.085s 0.008s 15