H: われわれの努力について - About Our Effort -

問題

※この問題はおまけの問題と捉えていただけるとありがたく、できれば先に他の問題のほうをお楽しみいただければと思っておりまして，ですので他の問題を通し終えて暇になり，かつその暇をこのコンテストで潰そうという気になってくれた方に挑戦していただければと思います。

D問題のクエリが遅くてすみませんでした。 しかし我々といたしましても決してただ怠慢をしていたわけではないのです。 私たちなりに努力したのです。 その努力の片鱗を味わっていただくため、このような問題を出題した次第であります。

問題: D問題のサーバー側の処理をするプログラムを作成せよ。

なおこの問題は本当にD問題の要求を満たすプログラムを作成することが目標ということですので、言語による向き/不向きなどは一切考慮いたしませんのであしからず。最速実行速度を達成された方はもれなくAOJに収録される際にジャッジプログラムとして採用される可能性がありますのでぜひ挑戦下さい。

入力形式

入力は以下の形式で与えられる。

N
p_1 ... p_N
Q
l_1 r_1
...
l_Q r_Q

1行目では順列pの長さNが与えられる。2行目では順列pを表すN個の整数が空白区切りで与えられる。3行目ではクエリの数を表す整数Qが与えられる。続くQ行のi行目は空白区切りの2つの整数l_i, r_iからなり、クエリが区間[l_i, r_i]のコンプレックス度を聞くものであることを表す。

入力は以下の制約を満たす。

• 1 \≤ N \≤ 100,000
• 1 \≤ p_i \≤ N, p_i \neq p_j (i \neq j)
• 1 \≤ Q \≤ 200,000
• 1 \≤ l_i \≤ r_i \≤ N

出力形式

Q個の各クエリiに関して、pの区間[l_i, r_i]のコンプレックス度をi行目に出力せよ。ただし、pの区間[l_i, r_i]のコンプレックス度とは、(\{ (i, j) | p_i > p_j {\rm for} l \≤ i<j \≤ r \}の要素数)と定義される。

入力例1

4
4 1 3 2
2
1 3
2 4

出力例1

2
1

入力例2

1
1
1
1 1

出力例2

0