Фермер Джон розв'язує 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$ рядків, де кожен рядок містить одне ціле число — відповідь на $i$-й запит.

Приклади

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