Задача №112794. Блоки
Сегодня Mr. Fox решил поиграться c блоками в 2D мире. Каждый блок это квадрат со стороной 1 дюйм. В этом мире есть N башен с блоками выстроенными в ряд, где i -ая башня имеет высоту h i блоков. Например: Если N = 6 и H = {3, 1, 5, 4, 1, 6} , то блоки будут построены так:
.....X
..X..X
..XX.X
X.XX.X
X.XX.X
XXXXXX
Mr. Fox хочет ответить на Q запросов о его блоках.(без изменения их). i -й запрос: Если рассматривать блоки с a i по b i включительно, избавляясь от всех других блоков, то сколько квадратных дюймов воды они могут держать? Ячейка может удерживать воду, если она не содержит блок и слева и справа от ячейки есть башня из блоков не меньшей высоты. Для примера a i = 2 , b i = 6 получается следующая картинка (* - ячейка с водой)
....X
.X**X
.XX*X
.XX*X
.XX*X
XXXXX
В первой строке вводятся число N и Q . Далее следуют N чисел H i . Затем следуют Q пар чисел a i и b i .
1 ≤ N , Q ≤ 300 000
1 ≤ H i ≤ 1 000 000 000
1 ≤ A i ≤ B i ≤ N
Выведите сумму все ответов на запросы по модулю 10 9 + 7
11 11 2 4 5 3 2 6 1 3 1 8 1 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11
60
5 3 10 1 1 1 10 1 5 1 2 4 5
27