Школьники из кружка по информатике «Капибары кодят» участвуют в олимпиаде. По итогам олимпиады $$$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$$$ конфет.
Хромой король перемещается по клетчатой доске размером $$$n \times m$$$, каждый раз переходя из текущей клетки в соседнюю по стороне. Будем задавать клетку в ряду $$$x$$$ столбце $$$y$$$ как $$$(x, y)$$$.
Хромой король должен посетить все клетки, побывав в каждой клетке ровно один раз, и вернуться в начальную клетку. При этом на доске выделены две соседние клетки: $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$. В обходе доски королем клетки $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$ должны встречаться подряд: оказавшись в одной из них, он должен сразу же перейти в другую.
Найдите подходящий порядок обхода доски или выясните, что его не существует.
Первая строка содержит два числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 1000$$$) — размеры доски.
Вторая строка содержит четыре числа $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ — координаты двух соседних клеток ($$$1 \le x_1, x_2 \le n$$$; $$$1 \le y_1, y_2 \le m$$$; $$$|x_1-x_2|+|y_1-y_2|=1$$$).
Если такого обхода доски не существует, выведите одно число $$$-1$$$.
Иначе выведите $$$n \times m + 1$$$ пару чисел — координаты клеток в порядке обхода, начальную клетку необходимо вывести дважды, в начале и в конце.
В этой задаче 50 тестов, каждый оценивается независимо в 2 балла.
В этой задаче во время тура вам сообщается результат проверки на каждом тесте.
4 32 2 3 2
1 1 2 1 2 2 3 2 3 1 4 1 4 2 4 3 3 3 2 3 1 3 1 2 1 1
3 51 2 2 2
-1
На рисунке показан обход доски для первого примера.
Дана квадратная доска размера $$$m \times m$$$. Строки и столбцы доски пронумерованы от $$$1$$$ до $$$m$$$.
Необходимо расставлять на доске фишки так, чтобы в каждой клетке находилось не более одной фишки. При этом должны выполняться $$$n$$$ ограничений. В $$$i$$$-м ограничении заданы два целых числа $$$r_i$$$ и $$$c_i$$$, означающие, что в прямоугольнике, состоящем из клеток с координатами $$$[1 \ldots r_i] \times [1 \ldots c_i]$$$, может находиться не более одной фишки.
Требуется найти остаток от деления количества различных расстановок фишек, удовлетворяющих всем ограничениям, на $$$10^9+7$$$.
Первая строка входных данных содержит целые числа $$$n$$$ и $$$m$$$ — количество ограничений и размер доски ($$$1 \le n \leq 2 \cdot 10^5$$$, $$$1 \leq m \le 10^9$$$).
Далее следуют $$$n$$$ строк, в каждой из которых записаны два числа $$$r_i$$$ и $$$c_i$$$ ($$$1 \le r_i, c_i \le m$$$).
Выведите одно число — количество допустимых расстановок фишек, взятое по модулю $$$10^9+7$$$.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 3 | $$$n \le 10, m \le 4$$$ | — |
| 2 | 6 | $$$n = 1, m \le 1000$$$ | — |
| 3 | 8 | $$$n \le 10, m \le 1000$$$ | 1, 2 |
| 4 | 8 | $$$n \le 15, m \le 10^9$$$ | 1–3 |
| 5 | 10 | $$$n \le 2500, m \le 100$$$ | 1 |
| 6 | 10 | $$$n \le 2500, m \le 250$$$ | 1, 5 |
| 7 | 10 | $$$n \le 2500, m \le 1000$$$ | 1–3, 5, 6 |
| 8 | 10 | $$$n \le 2500, m \le 10^5$$$ | 1–3, 5–7 |
| 9 | 15 | $$$n \le 2 \cdot 10^5, m \le 2 \cdot 10^5$$$ | 1–3, 5–8 |
| 10 | 20 | нет | 1–9 |
1 44 4
17
2 21 22 1
10
3 52 53 44 4
4480
В первом примере на всей доске может быть поставлено не более одной фишки. Есть $$$4 \times 4 = 16$$$ вариантов поставить одну фишку и $$$1$$$ вариант с нулём расставленных фишек.
В компьютерной игре «Мегапрыжок» герой прыгает между вершинами горной цепи с целью попасть на точку с флагом, где завершается уровень.
Горная цепь в игре состоит из $$$n$$$ подряд идущих зубцов, $$$i$$$-й из которых находится в позиции $$$i$$$ и имеет высоту $$$h_i$$$. При этом для любых $$$i \lt j$$$ герой может прыгнуть по прямой с зубца $$$i$$$ на зубец $$$j$$$, при условии, что во время полёта по прямой на его пути не будет других зубцов. Более формально, не найдётся такого $$$k$$$, что $$$i \lt k \lt j$$$ и вершина $$$k$$$-го зубца — точка с координатами $$$(k, h_k)$$$ — находится строго выше отрезка, соединяющего точки $$$(i, h_i)$$$ и $$$(j, h_j)$$$.
Компания «Победи ИИ» занимается тренировкой нейросети для управления героем в этой игре. Для создания тренировочных данных необходимо ответить на несколько запросов: для пары индексов $$$l, r$$$ $$$(1 \le l \le r \le n)$$$ выяснить, за какое минимальное число прыжков, начав на зубце с номером $$$l$$$, герой сможет попасть на зубец с номером $$$r$$$.
В первой строке входных данных находится число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — число зубцов.
Во второй строке находятся $$$n$$$ чисел: $$$h_1, h_2, \dots, h_n$$$ $$$(0 \le h_i \le 10^{12})$$$ — высоты зубцов.
В третьей строке находится число $$$q$$$ $$$(1 \le q \le 10^5)$$$ — количество запросов.
В каждой из следующих $$$q$$$ строк находятся два числа $$$l_i, r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$ — параметры очередного запроса.
Для каждого запроса в отдельной строке выведите целое неотрицательное число минимальное необходимое число прыжков.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 9 | $$$n, q \le 300$$$ | — |
| 2 | 9 | $$$n, q \le 5000$$$ | 1 |
| 3 | 14 | $$$h_i \le 10$$$ | — |
| 4 | 21 | Существует $$$k$$$, такое что для всех $$$i$$$ выполнено $$$l_i \le k \le r_i$$$ | — |
| 5 | 27 | $$$n, q \le 5 \cdot 10^4$$$ | 1, 2 |
| 6 | 20 | включает подзадачи 1–5 | 1–5 |
8 5 3 4 3 6 2 1 4 3 1 8 2 7 4 4
2 2 0
Разберём второй запрос в примере из условия. Путь героя от зубца 2 до зубца 7 может выглядеть следующим образом:
