|
База кандидатов
(Время: 0,25 сек. Память: 32 Мб Сложность: 87%)
В крупной компании ведётся база из N кандидатов на различные должности. Для каждого кандидата известен его уровень профессионализма. Эти значения записаны в списке. Заявки кандидатов обрабатываются партиями, поэтому руководство компании часто рассматривает не всех кандидатов сразу, а только некоторую часть списка – например, с позиции L по позицию R. Руководство за одно заседание проводит K рассмотрений.
Когда менеджеры по найму анализируют группу кандидатов, они обычно рассматривают не только всю группу целиком, но и различные подряд идущие подгруппы внутри неё. Например, могут посмотреть несколько соседних кандидатов, чтобы понять, кто из них станет решающим при выборе. На практике в каждой такой небольшой группе всегда находится человек, который фактически определяет итог решения: если в группе есть кандидат с заметно более слабым уровнем профессионализма, именно он становится главным ограничением – из-за него вся группа выглядит менее сильной. Поэтому менеджеры говорят, что именно этот кандидат «определяет уровень» этой конкретной группы. Каждый раз, когда кандидат оказывается таким определяющим человеком для какой-то подряд идущей группы кандидатов, считается, что он получает одну отметку своего «влияния». Чем больше групп, в которых кандидат становится тем самым человеком, определяющим уровень всей группы, тем выше его вклад в анализ. Внутри участка от L до R существует много возможных подряд идущих групп кандидатов. Для каждой такой группы определяется кандидат, который фактически задаёт уровень всей группы. Этот кандидат получает одну отметку влияния. Задача состоит в том, чтобы для каждого рассматриваемого участка списка посчитать суммарное влияние всех кандидатов внутри него. То есть нужно определить, сколько раз кандидаты из этого участка в сумме становились теми людьми, которые определяли уровень различных подряд идущих групп кандидатов внутри данного диапазона.
Входные данные
Входной файл INPUT.TXT в первой строке содержит два натуральных числа: N, K. Во второй строке список уровней профессионализма (1 ≤ leveli ≤ 109). Далее в K строках по два натуральных числа: L, R (1 ≤ N, K ≤ 2×105; 1 ≤ L ≤ R ≤ N).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ для каждого рассмотрения.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 3
2 1 1 4 3
1 3
3 5
1 2 | 8
6
3 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
