Строительство нового города Дореми начинается! Город можно представить как простой неориентированный граф из \(n\) вершин. Высота \(i\)-й вершины равна \(a_i\). Теперь Дореми должна решить, какие вершины должны быть соединены ребрами.
По экономическим причинами в графе не должно быть петель или кратных ребер.
Из соображений безопасности не должно быть попарно различных вершин \(u\), \(v\) и \(w\) таких, что \(a_u \leq a_v \leq a_w\), и существуют ребра \((u,v)\) и \((v,w)\).
Дореми хочет знать, какое максимальное количество ребер в графе может быть при данных ограничениях. Можете помочь ей?
Обратите внимание, что построенный граф не обязательно должен быть связным.
Выходные данные
Для каждого набора входных данных выведите максимально возможное число ребер в графе.
Примечание
В первом наборе входных данных максимум может быть \(3\) ребра. Одно из возможных решений — добавить ребра \((1,3)\), \((2,3)\), \((3,4)\). На рисунке ниже красное число над вершиной \(i\) равно \(a_i\).
Список ниже перечисляет все тройки \(u\), \(v\), \(w\) такие, что существуют ребра \((u,v)\) и \((v,w)\).
- \(u=1\), \(v=3\), \(w=2\);
- \(u=1\), \(v=3\), \(w=4\);
- \(u=2\), \(v=3\), \(w=1\);
- \(u=2\), \(v=3\), \(w=4\);
- \(u=4\), \(v=3\), \(w=1\);
- \(u=4\), \(v=3\), \(w=2\).
Другое возможное решение — добавить ребра \((1,4)\), \((2,4)\), \((3,4)\).
Неправильное решение — добавить ребра \((1,3)\), \((2,3)\), \((2,4)\), \((3,4)\). В таком случае если выбрать \(u=4\), \(v=2\), \(w=3\), то \(a_u\le a_v \le a_w\) выполняется, и есть соответствующие ребра.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
2 2 3 1
6
5 2 3 1 5 2
12
7 2 4 9 1 4 6 3 7 4 2 3
4
1000000 1000000 1000000 1000000
|
3
9
35
2
|