問題文

$N$ 人のプレイヤー $1,2,\dots,N$ がいます。

今から $(1,2,\dots,N)$ の順列 $P$ を用いて $Q$ 回の大会が行われます。$i$ 回目の大会は以下のように進行します。

1. 先頭から順にプレイヤー $P_{L_i}, P_{L_{i+1}}, \dots, P_{R_i}$ と並んだ列を作る。
2. 以下の処理を列に残っているプレイヤーが一人になるまで繰り返す。
• 先頭から二人のプレイヤーで試合を行う。プレイヤー番号が大きい方のプレイヤーが勝利し、列の末尾に移動する。小さい方のプレイヤーは列から抜ける。

$i=1,2,\dots,N$ それぞれについて、$Q$ 回の大会の中でプレイヤー $i$ が勝利する試合数の合計を求めてください。

入力

$N$
$P_1\ P_2\ \dots \ P_N$
$Q$
$L_1\ R_1$
$L_2\ R_2$
$\vdots$
$L_Q\ R_Q$

• 入力はすべて整数である。
• $2 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $P$ は $(1,2,\dots,N)$ の順列である。
• $1 \le L_i < R_i \le N$

出力

$i$ 行目にはプレイヤー $i$ が勝利する試合数の合計を出力してください。 最後に改行してください。

サンプル

5
3 1 4 2 5
1
1 5

0
0
1
1
2

14
5 9 12 7 4 1 14 6 13 3 11 2 8 10
10
12 13
1 14
3 8
2 13
4 11
3 11
4 6
5 8
4 14
2 14

0
0
0
4
0
0
6
4
1
2
7
12
10
26