--- tags: 問題 --- # Walking-1D(Large) 実行時間制限 : 2sec / メモリ制限 : 1024MB 配点 : $300$点 ## 問題文 長さ$N$の文字列$S$があります。この文字列には$M$個の壁があり、それぞれ座標$A_i(1\leq i \leq M)$に存在します。 太郎くんはこの文字列$S$の上を左右に何度でも移動できます。ただし、道の上しか移動ができず、壁は乗り越えることができません。 このとき、以下の$Q$個のクエリに答えてください。 太郎くんのスタート地点の座標が$x$のとき、移動できるマスは何個存在しますか？ ## 制約 * $1\leq N \leq 10^{18}$ * $0 \leq M \leq 2×10^5$ * $1 \leq A_i \leq N$ * $1 \leq Q \leq 2×10^5$ * $1 \leq x \leq N$ * $x \neq A_i$ 入力はすべて正の整数 ## 入力 入力は以下の形式で標準入力から与えられる。 ``` N M A_1 A_2 ... A_M Q x_1 x_2 ... x_Q ``` ## 出力 それぞれのクエリに対して太郎くんが移動できるマス目の数を出力してください。 ## 入力例1 ``` 6 2 4 6 3 2 5 1 ``` ## 出力例1 ``` 3 1 3 ``` スタート地点も移動できるマスに含みます。 ## 入力例2 ``` 1000000000000000000 3 1000 1000000000 10000000 4 500 21345 40000000 2147483647 ``` ## 出力例2 ``` 1000 9999001 999999999000000001 ``` 入力や出力が32bit整数に収まらないことがあります。 ## 入力例3 ``` 15 ..#....#.###... 4 1 6 15 7 ``` ## 出力例3 ``` 2。 4 3 4 ```