e-olymp
Задачи

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

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

Фермер Джон верит, что он сделал великое открытие в проектировании алгортимов: он открыл почти линейный алгоритм для известной проблемы 3SUM, про которую никто не знает решение, работающее быстрее, чем за квадратичное время. Одна из формулировок проблемы 3SUM такова: задан массив целых чисел s1,..., sm, требуется посчитать количество таких неупорядоченных троек с различными индексами i, j, k, что si + sj + sk = 0.

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

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

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

Первая строка содержит два целых числа n (1n5000) и q (1q105). Вторая строка содержит элементы A1, ..., An массива A. Каждая из следующих q строк содержит два натуральных числа ai и bi, представляющих запрос.

Гарантируется, что −106Ai106 для каждого элемента массива Ai.

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

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

Пример

Для первого вопроса возможны тройки (A1, A2, A5) и (A2, A3, A4).

Лимит времени 1 секунда
Лимит использования памяти 512 MiB
Входные данные #1
7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7
Выходные данные #1
2
1
4
Источник 2020 USACO Январь, Золото