Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1613. Difference
Бинарный поискДерево отрезков, декартово дерево, √-декомпозиция
Олимпиадные задачи на английском языке
| 04/07/2011 | Лето 2011 - дорешивание (08D) |
| 13/07/2011 | Лето 2011 - 8 (D) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Mirko discovered what Slavko did in previous task, and decided to deal with something completely
opposite to tables of letters: sequences of numbers.
Let’s define a value of a sequence of numbers as the difference between the largest and the smallest number within
that sequence. For example, value of sequence (3, 1, 7, 2) is 6, and value of (42, 42) is 0.
Find the sum of values of all subsequences of consecutive elements of a given sequence.
Input
The first line of input contains a single integer `N` (`2\ ≤\ N\ ≤\ 300000`), number of elements of the
sequence. Next `N` lines contain elements of the sequence. Each element is a positive integer not greater than 100000000.
Output
The first and only line of output must contain the requested sum.
Sample Input 1
3 1 2 3
Sample Output 1
4
Sample Input 2
4 7 5 7 5
Sample Output 2
12
