問題
ある海にN個の島が浮かんでおり、それぞれ1~N番の番号が被り無く付けられている。
番号が隣り合う島の間に橋が架かっている。なお、1番とN番の島も番号が隣り合うとする。
ある日、事故によりM本の橋が壊れてしまった。壊れた橋は渡ることが出来ない。
あなたは、島aから島bにわたることが出来るか調べることにした。
入力
N M h1 h2 . . . hM Q a1 b1 a2 b2 . . . aQ bQ
Nは島の数、Mは壊れた橋の数、Qは調査する回数を表す。
hiは島hiと島hi+1(i=Nの時のみ島1)に架かる橋が壊れたことを表す。
aiとbiは、島aiから島biにいけるかを調べることを表す
出力
島aiから島biをわたることが出来ると判定した回数を出力せよ。
制約
全ての入出力ケースについて以下を満たす。
- 2≦N≦100000
- 0≦M≦N
- 1≦Q≦100000
- hi!=hj
- ai!=bi
入出力例
入力例1
10 2 9 4 4 8 7 7 10 5 9 3 10
出力例1
3
解説
島9と島10の間の橋、島4と島5の間の橋が壊れている。
島8から島7へは、島8から島7へ架かっている橋を使えばいける。
島7から島10へはいけない
島5から島9へは、島5,島6,島7,島8,島9のように行けばよい。
島3から島10へは、島3,島2,島1,島10のように行けばよい。
よって、今回の４つの調査の内、３つでいけると判定されたため3と出力する。
入力例2
10 3 5 10 8 5 6 5 6 2 5 7 6 9 4 6
出力例2
0
解説
この場合どの調査でも橋が壊されているためわたることが出来ない。よって0を出力する。
入力例3
10 0 3 2 9 7 4 3 2
出力例3
3
解説
この場合橋が１つも壊されていないため全ての調査においてわたることが出来る。よって3を出力する。