Егор очень любит Москву и часто ходит на прогулку, чтобы полюбоваться ее видами.
Москва в представлении Егора представляет собой длинное прямое шоссе, вдоль которого расположено n башен, пронумерованных в порядке их следования числами от 1 до n. Все башни имеют различные высоты, которые выражаются целыми числами от 1 до n. Высота башни с номером i составляет hi.
Однако Егор не любит возрастающие последовательности. Его разочаровывают тройки башен, таких что с возрастанием их индексов их значения тоже возрастают. Более формально, тройка башен с номерами i, j и k разочаровывает Егора, если i < j < k и hi < hj < hk.
Егор заранее знает высоты всех башен в Москве и хочет узнать, сильно ли он разочаруется на прогулке. Помогите ему определить, сколько есть троек башен, которые его разочаруют.
Первая строка входных данных содержит единственное число n — количество башен в Москве (1 ≤ n ≤ 8000).
Вторая строка входных данных содержит n различных натуральных чисел, i-е из них hi — высота i-й башни (1 ≤ hi ≤ n).
Выведите одно число — количество троек башен, которые разочаруют Егора.
Обратите внимание, что ответ может не поместиться в стандартный 32-битный тип данных. Надо использовать 64-битный тип, в паскале он называется «int64», в C++ «long long», в Java «long».
5
1 3 4 2 5
5
3
3 1 2
0
| Турнир Архимеда 2016 |
|---|
| Закончено |
