Сегодня 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