問題文

数列 X=(X_1,X_2,\ldots,X_M) の美しさを以下のように定めます。

• Y_i\coloneqq \max(X_1,X_2,\ldots,X_i) としたときの、Y_1,Y_2,\ldots,Y_M に含まれる数の種類数

長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。Q 個のクエリを処理してください。

i 番目のクエリでは整数 L_i,R_i が与えられるので、数列 (A_{L_i},A_{L_i+1},\ldots,A_{R_i}) の美しさを出力してください。

制約

• 1\leq N\leq 2\times 10^5
• 1\leq A_i\leq N\,(1\leq i\leq N)
• 1\leq Q\leq 2\times 10^5
• 1\leq L_i\leq R_i\leq N\,(1\leq i\leq Q)
• 入力はすべて整数 (17:15 追記)

入力例 1

5
1 5 2 4 3
4
1 5
2 5
3 3
3 5

出力例 1

2
1
1
2

(1,5,2,4,3) の美しさは 2 であるため、1 番目のクエリに対しては 2 を出力します。

(5,2,4,3) の美しさは 1 であるため、2 番目のクエリに対しては 1 を出力します。

入力例 2

5
3 2 2 4 5
4
1 5
1 5
4 5
4 5

出力例 2

3
3
2
2

(L_i,R_i)=(L_j,R_j) となる i,j\,(i\neq j) が存在する場合もあります。

入力例 3

5
4 4 1 3 5
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

出力例 3

1
1
1
1
2
1
1
1
2
1
2
3
1
2
1