← 返回题目列表

AtCoder · pakencamp_2022_day1_k

K. 美丽

中文机器翻译题面 查看原题

配点 : 500 点

問題文

数列 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 添加) 打印第

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \ldots A_N
Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

Q 行。 列出i\,(1\leq i\leq Q) 行中,i 个查询的答案。


入力例 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