Школьники из кружка по информатике «Капибары кодят» участвуют в олимпиаде. По итогам олимпиады $$$i$$$-й школьник набрал $$$a_i$$$ баллов.
Чтобы поощрить участников, руководитель кружка Александр Игоревич решил раздать школьникам конфеты. Для всех $$$i$$$ и $$$j$$$, если $$$i$$$-й школьник набрал больше баллов, чем $$$j$$$-й, то руководитель даёт $$$i$$$-му школьнику $$$a_i - a_j$$$ конфет.
Помогите руководителю понять, сколько суммарно конфет ему необходимо подготовить для раздачи школьникам.
В первой строке входных данных задается число $$$n$$$ — количество школьников ($$$1 \le n \le 500\,000$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$a_i$$$ — результаты участников кружка на олимпиаде ($$$0 \le a_i \le 10^7$$$).
Выведите единственное число — общее количество конфет, которое необходимо подготовить, чтобы раздать школьникам.
Обратите внимание, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены
| |c|} Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи |
| 1 | 15 | $$$1 \le n \le 1\,000$$$ | |
| 2 | 5 | Все $$$a_i$$$ одинаковые | |
| 3 | 5 | Для любых $$$i \ne j$$$ выполнено $$$a_i \ne a_j$$$, также $$$1 \le a_i \le n$$$ | |
| 4 | 10 | $$$0 \le a_i \le 1$$$ | |
| 5 | 15 | $$$0 \le a_i \le 100$$$ | 4 |
| 6 | 15 | Среди $$$a_i$$$ присутствует не более двух различных значений | 2, 4 |
| 7 | 35 | — | 1–6 |
51 2 3 4 5
20
100 0 0 0 0 10000000 0 0 0 0
90000000
В первом примере первый школьник не получит конфет, второй школьник получит $$$1$$$ конфету, третий школьник получит $$$1+2=3$$$ конфеты, четвертый школьник получит $$$1+2+3=6$$$ конфет, пятый школьник получит $$$1+2+3+4=10$$$ конфет.
