Наша вселенная представляет собой n-мерный прямоугольный параллелепипед. Множество измерений вселенной B = {a[i] : 1<=i<=n}.
Множество B такого, что его первые b элементов являются измерениями b-мерного подпараллелепипеда.
Перед учеными встал ряд вопросов типа: какое пространство находится внутри k-мерного подпараллелепипеда, если предположить, что пространство внутри m-мерного нулевое.
Напишите программу, которая даст ответ на вопросы ученых.
Входные данные:
Все числа неотрицательные.
В первой строке вводятся целые числа (n, q <= 10^5) размерность нашей вселенной и количество вопросов, интересующих ученых соответственно.
Во второй строчке вводятся n целых чисел - измерения вселенной, каждое из которых не превосходит (10^18 - 14)
Далее следует q строк по два числа, однозначно задающие вопрос указанного типа, интересующий ученых - m, k. (m, k <= n)
Выходные данные:
Программа должна выводить q строк по одному числу. На i-ой строке должен распологаться ответ на i вопрос указанного типа.
Пример:
INPUT:
3 1
1 2 3
0 3
OUTPUT:
6
Пояснение:
Т.к. пространство внутри 0 мерного подпараллелепипеда (точки) нулевое (по условию), то пространство внутри 3-х мерного (пространство внутри 3-х мерного - объем) считается по обычной формуле: 1*2*3 = 6
Автор: Иван Шершнев