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\,(1\leq i\leq Q) $ 行目には、 $ i $ 番目のクエリに対する答えを出力してください。

### Sample Explanation 1 $ (1,5,2,4,3) $ の**美しさ**は $ 2 $ であるため、 $ 1 $ 番目のクエリに対しては $ 2 $ を出力します。 $ (5,2,4,3) $ の**美しさ**は $ 1 $ であるため、 $ 2 $ 番目のクエリに対しては $ 1 $ を出力します。 ### Sample Explanation 2 $ (L_i,R_i)=(L_j,R_j) $ となる $ i,j\,(i\neq j) $ が存在する場合もあります。 ### Constraints - $ 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 追記)