Фермер Джон верит, что он сделал великое открытие в проектировании алгортимов: он открыл почти линейный алгоритм для известной проблемы 3SUM, про которую никто не знает решение, работающее быстрее, чем за квадратичное время. Одна из формулировок проблемы 3SUM такова: задан массив целых чисел s[1]
,..., s[m]
, требуется посчитать количество таких неупорядоченных троек с различными индексами i, j, k, что s[i]
+ s[j]
+ s[k]
= 0.
Чтобы проверить алгоритм ФД, Бесси подготовила массив A из n целых чисел. Бесси совершит q запросов задав пару индексов a[i]
, b[i]
(1 ≤ a[i]
≤ b[i]
≤ n). Для каждого такого запроса ФД должен решить задачу 3SUM на подмассиве A[a[i]
... b[i]
].
ФД просит Вас пройти тест Бесси.
Первая строка содержит два целых числа n (1 ≤ n ≤ 5000) и q (1 ≤ q ≤ 10^5
). Вторая строка содержит элементы A[1]
, ..., A[n]
массива A. Каждая из следующих q строк содержит два натуральных числа a[i]
и b[i]
, представляющих запрос.
Гарантируется, что −10^6
≤ A[i]
≤ 10^6
для каждого элемента массива A[i]
.
Выведите q строк. Cтрока i содержит одно целое число - ответ на i-ый запрос.
Для первого вопроса возможны тройки (A[1]
, A[2]
, A[5]
) и (A[2]
, A[3]
, A[4]
).