AT_pakencamp_2022_day1_k Beautifulness

我们将数列 $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})$ 的**美丽值**。

输入按如下格式从标准输入给出： > $N$ $A_1$ $A_2$ $\ldots$ $A_N$ $Q$ $L_1$ $R_1$ $L_2$ $R_2$ > $\vdots$ > $L_Q$ $R_Q$

请输出 $Q$ 行，第 $i$ 行输出第 $i$ 个查询的答案。

### 样例解释 1 $(1,5,2,4,3)$ 的美丽值为 $2$，所以对于第 $1$ 个查询，输出 $2$。 $(5,2,4,3)$ 的美丽值为 $1$，所以对于第 $2$ 个查询，输出 $1$。 ### 样例解释 2 也有可能存在 $i, j\,(i\neq j)$ 使得 $(L_i,R_i)=(L_j,R_j)$。 ### 数据范围 - $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 更新） 由 ChatGPT 5 翻译