Егор очень любит Москву и часто ходит на прогулку, чтобы полюбоваться ее видами.
Москва в представлении Егора представляет собой длинное прямое шоссе, вдоль которого расположено 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 ».
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
1 3 4 2 5 |
5 |
| 2 |
3
3 1 2 |
0 |