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