Фермер Джон розв'язує 3SUM#9603

Фермер Джон розв'язує 3SUM

1 секунда

512 мегабайтів

Дуже легка

Фермер Джон переконаний, що зробив революційне відкриття в галузі розробки алгоритмів: він стверджує, що розробив майже лінійний алгоритм для відомої задачі 3SUM, яка, як прийнято вважати, вимагає щонайменше квадратичного часу. Одне з формулювань задачі 3SUM виглядає наступним чином: дано масив цілих чисел $s_{1}, \dots, s_{m}$ s_1, \ldots, s_m. Потрібно підрахувати кількість невпорядкованих трійок різних індексів $i, j, k$ i, j, k, для яких виконується умова $s_{i} + s_{j} + s_{k} = 0$ s_i + s_j + s_k = 0.

Щоб перевірити алгоритм Фермера Джона, Бессі підготувала масив $A$ з $n$ цілих чисел. Вона виконає $q$ запитів, кожен з яких задає пару індексів $x_{i}, y_{i}$ x_i, y_i $(1 \leq x_{i} \leq y_{i} \leq n)$ (1 \le x_i \le y_i \le n). Для кожного запиту Фермер Джон повинен розв'язати задачу 3SUM на підмасиві $A [x_{i} \dots y_{i}]$ A[x_i \ldots y_i].

Фермер Джон просить вас допомогти йому пройти перевірку Бессі.

Вхідні дані

У першому рядку містяться два цілих числа $n (1 \leq n \leq 5000)$ n~(1 \le n \le 5000) та $q (1 \leq q \leq 1 0^{5})$ q~(1 \le q \le 10^5).

У другому рядку містяться елементи масиву $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n. У кожному з наступних $q$ рядків містяться два цілих числа $x_{i}$ x_i та $y_{i}$ y_i, що задають один запит.

Гарантується, що для кожного елемента $a_{i}$ a_i масиву виконується умова $- 1 0^{6} \leq a_{i} \leq 1 0^{6}$ -10^6 \le a_i \le 10^6.

Вихідні дані

Виведіть $q$ рядків. У $i$ -му рядку повинно міститися одне ціле число — відповідь на $i$ -й запит.

Приклади

Для першого запиту прийнятними трійками індексів є $(A_{1}, A_{2}, A_{5})$ (A_1, A_2, A_5) та $(A_{2}, A_{3}, A_{4})$ (A_2, A_3, A_4).

Приклад 1