Description

给出一个长度为\( n \)的序列\( a \)
给出\( q \)组询问，每组询问给出两个数\( x,y \)，求\( a \)序列的所有区间中，数字\( x \)的出现次
数与数字\( y \)的出现次数相同的区间有多少个

Format

Input

第一行两个数\( n \)和\( q \)
第二行\( n \)个数\( a_i \)
接下来\( q \)行，每行两个数\( x,y \)表示一组询问

Output

\( q \)行，每行一个数表示对应询问的答案

Sample 1

Input

3 2
1 2 1
1 2
4 5

Output

2
6

Limitation

2s, 256MB for each test case.
对于30%的数据，\(1 \leq n \leq 100,1 \leq q \leq 1000 \)
对于另外30%的数据，序列中只有最多 50 种不同的颜色且\( 1 \leq n \leq 1000\)
对于100%的数据，\(1 \leq n \leq 8000,1 \leq q \leq 500000，1 \leq x,y,a_i \leq 10^9\)

Hint