Задача D. Disordered polygon ≡
| Автор: | Антон Карабанов, И. Блинов, А. Баранов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
| Выходной файл: | Стандартный выход |
Условие
Женя нарисовал на доске правильный n-угольник, подписал его вершины числами по часовой стрелке в порядке возрастания : "1 2 3 ... n". Подошедший Никита переставил в подписи числа местами, стёр все стороны Жениной фигуры и соединил вершины в получившемся новом порядке (в том числе первую и последнюю вершины). Теперь на доске красуется замкнутая ломаная. Сколько пар отрезков ломаной пересекаются?
Формат входных данных
Первая строка входных данных содержит одно число n. Вторая строка содержит n чисел a1, a2… an — перестановку вершин многоугольника.
Формат выходных данных
Выведите одно неотрицательное целое число — ответ на вопрос задачи.
Ограничения
3 ≤ n ≤ 105
Пояснение к примерам
Примеры тестов
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|
| 4 | |
|