Фермер Джон верит, что он сделал великое открытие в проектировании алгортимов:
он открыл почти линейный алгоритм для известной проблемы 3SUM, про которую
никто не знает решение, работающее быстрее, чем за квадратичное время.
Одна из формулировок проблемы 3SUM такова:
задан массив целых чисел \(s_1,\dots,s_m\)
требуется посчитать количество таких неупорядоченных троек с различными индексами
\(i,j,k\) такими, что \(s_i + s_j + s_k = 0\).
Чтобы проверить алгоритм ФД, Беси подготовила массив \(A\) из \(N\) целых чисел
(\(1 \leq N \leq 5000\)). Беси также спросит \(Q\) раз (\(1 \leq Q \leq 10^5\)),
пару индексов \(1 \leq a_i \leq b_i \leq N\). Для каждого такого вопроса
ФД должен решить проблему 3SUM на подмассиве \(A[a_i \dots b_i]\).
ФД просит Вас пройти тест Беси.
ОЦЕНИВАНИЕ:
- В тестах 2-4 \(N\le 500.\)
- В тестах 5-7 \(N\le 2000.\)
- В тестах 8-15 нет дополнительных ограничений.
ФОРМАТ ВВОДА (файл threesum.in):
Первая строка содержит два разделённых пробелом целых числа
\(N\) и
\(Q\).
Вторая строка содержит разделённые одиночными пробелами элементы
\(A_1,\dots,A_N\) массива
\(A\).
Каждая из последующих
\(Q\) строк содержит два положительных целых числа
\(a_i\) и
\(b_i\), представляющих вопрос.
Гарантируется, \(-10^6 \leq A_i \leq 10^6\) для каждого элемента массива \(A_i\).
ФОРМАТ ВЫВОДА (файл threesum.out):
Вывод должен содержать \(Q\) строк. Каждая строка \(i\) содержит одно целое число
--- ответ на \(i\)-ый вопрос.
Заметим, что Вы должны использовать 64-ные целые числа, чтобы избежать
переполнения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7
|
2
1
4
|