Farmer John acredita ter feito um grande avanço: um algoritmo quase linear para 3SUM, famoso por não ter solução conhecida substancialmente melhor que o tempo quadrático. Uma formulação: dado o vetor de inteiros $s_1,\dots,s_m$, contar triplas não ordenadas de índices distintos $i,j,k$ com $s_i+s_j+s_k=0$.

Para testar, Bessie fornece um vetor $A$ de $N$ inteiros ($1\leq N\leq5000$) e $Q$ consultas ($1\leq Q\leq10^5$), cada uma com $1\leq a_i\leq b_i\leq N$. Deve-se resolver 3SUM em cada subvetor $A[a_i\dots b_i]$.

Infelizmente, FJ acaba de achar uma falha. Confia que a corrigirá, mas pede sua ajuda para passar no teste enquanto isso!

Entrada

Primeira linha: inteiros $N,Q$ separados por espaços. Segunda: elementos $A_1,\dots,A_N$ separados por espaços. As próximas $Q$ linhas contêm inteiros $a_i,b_i$ separados por espaços para uma consulta.

Cada elemento satisfaz $-10^6\leq A_i\leq10^6$.

Saída

$Q$ linhas; a linha $i$ tem um inteiro, a resposta à consulta $i$. Use inteiros de 64 bits para evitar transbordamento.

Exemplos

Entrada 1

7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7

Saída 1

2
1
4

Note

As triplas da primeira consulta são $(A_1,A_2,A_5)$ e $(A_2,A_3,A_4)$.

Subtarefas

• Casos 2–4: $N\le500$.
• Casos 5–7: $N\le2000$.
• Casos 8–15: sem restrições adicionais.

Autor do problema: Dhruv Rohatgi