Author: | Антон Карабанов, И. Блинов, А. Баранов | Time limit: | 1 sec | |
Input file: | Standard input | Memory limit: | 512 Mb | |
Output file: | Standard output |
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?
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 a single non-negative integer — the answer to the problem question.
3 ≤ n ≤ 105
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|