Farmer John은 큰 돌파구를 찾았다며 3SUM의 거의 선형 시간 알고리즘을 주장합니다. 이 문제는 제곱 시간보다 훨씬 좋은 알려진 해법이 없기로 유명합니다. 한 정의는 정수 배열 $s_1,\dots,s_m$에서 서로 다른 인덱스 $i,j,k$의 순서 없는 세 수 조합 중 $s_i+s_j+s_k=0$인 수를 세는 것입니다.

Bessie는 검증하려 $N$개 정수 배열 $A$ ($1\leq N\leq5000$)와 $Q$개 질의 ($1\leq Q\leq10^5$)를 줍니다. 각각 인덱스 $1\leq a_i\leq b_i\leq N$로, 부분 배열 $A[a_i\dots b_i]$의 3SUM을 풀어야 합니다.

하지만 FJ는 방금 오류를 찾았습니다. 고칠 수 있다고 확신하나 그동안 Bessie의 시험을 통과하도록 도와주세요!

입력

첫 줄은 공백으로 구분된 정수 $N,Q$입니다. 둘째 줄은 공백으로 구분된 원소 $A_1,\dots,A_N$입니다. 다음 $Q$줄마다 공백으로 구분된 정수 $a_i,b_i$가 질의를 나타냅니다.

각 원소는 $-10^6\leq A_i\leq10^6$입니다.

출력

$Q$줄이며 $i$행은 질의 $i$의 답인 정수 하나입니다. 넘침을 막으려 64비트 정수를 쓰세요.

예제

입력 1

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

출력 1

2
1
4

참고

첫 질의의 조합은 $(A_1,A_2,A_5)$와 $(A_2,A_3,A_4)$입니다.

서브태스크

• 테스트 2–4: $N\le500$.
• 테스트 5–7: $N\le2000$.
• 테스트 8–15: 추가 제한 없음.

문제 작성: Dhruv Rohatgi