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

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

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

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

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

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

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

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

Пример

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