Фермер Джон решает 3SUM

Фермер Джон уверен, что он сделал великое открытие в проектировании алгортимов: он разработал почти линейный алгоритм для известной задачи 3SUM, решение которой, как считается, не может работать быстрее, чем за квадратичное время. Одна из формулировок задачи 3SUM звучит так: дан массив целых чисел $s_1,...,s_m$, необходимо посчитать количество таких неупорядоченных троек с различными индексами $i,j,k$, что $s_i+s_j+s_k=0$.

Чтобы проверить алгоритм ФД, Бесси подготовила массив $A$ из $n$ целых чисел. Бесси совершит $q$ запросов задав пару индексов $x_i,y_i(1\le x_i\le y_i\le n)$. Для каждого такого запроса ФД должен решить задачу 3SUM на подмассиве $A[x_i...y_i]$.

ФД просит Вас пройти тест Бесси.

Входные данные

Первая строка содержит два целых числа $n(1\le n\le 5000)$ и $q(1\le q\le 10^5)$. Вторая строка содержит элементы массива $a_1,...,a_n$. Каждая из следующих $q$ строк содержит два натуральных числа $x_i$ и $y_i$, представляющих запрос.

Гарантируется, что для каждого элемента массива $a_i$ выполняется условие $-10^6\le a_i\le 10^6$.

Выходные данные

Выведите $q$ строк. Cтрока $i$ содержит одно целое число — ответ на $i$-ый запрос.

Примеры

Для первого запроса возможны следующие тройки: $(a_1,a_2,a_5)$ и $(a_2,a_3,a_4)$.