AT_arc060_c [ARC060E] 高橋君とホテル

[problemUrl]: https://atcoder.jp/contests/arc060/tasks/arc060_c $ N $ 軒のホテルが一直線上に並んでいます。$ i\ \,\ (1\ \leq\ i\ \leq\ N) $ 番目のホテルは、座標 $ x_i $ に位置しています。 旅行者である高橋君には、次の $ 2 $ つの信念があります。 - 高橋君の $ 1 $ 日の移動距離は $ L $ を超えない。 - 高橋君は野宿をしない。すなわち、$ 1 $ 日の終わりには必ずいずれかのホテルにいなければならない。 $ Q $ 個のクエリが与えられます。$ j\,(1\ \leq\ j\ \leq\ Q) $ 番目のクエリとして、異なる $ 2 $ つの整数 $ a_j,\,b_j $ が与えられます。 各クエリについて、前述の信念をともに守った上で、高橋君が $ a_j $ 番目のホテルから $ b_j $ 番目のホテルに移動するために必要な最小日数を求めてください。 なお、高橋君が $ a_j $ 番目のホテルから $ b_j $ 番目のホテルに移動できることは保証されます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ x_1 $ $ x_2 $ $ ... $ $ x_N $ $ L $ $ Q $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ : $ a_Q $ $ b_Q $

出力は $ Q $ 行からなる。 $ j\ \,\ (1\ \leq\ j\ \leq\ Q) $ 行目には、高橋君が $ a_j $ 番目のホテルから $ b_j $ 番目のホテルに移動するために必要な最小日数を表す整数を出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ L\ \leq\ 10^9 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ 1\ \leq\ x_i\