AT_tkppc6_2_m 山分け

[problemUrl]: https://atcoder.jp/contests/tkppc6-2/tasks/tkppc6_2_m $ 1 $ から $ N $ までの番号が振られた $ N $ 人の海賊が、$ 1 $ から $ 10^{12} $ までの番号が振られた $ 10^{12} $ 個のお宝を山分けします。それぞれの海賊には分配されるお宝へのこだわりがあり、海賊 $ i $ は番号が $ L_i $ 以上 $ R_i $ 以下であるようなお宝のみを欲しがってその他のお宝は受け取りません。ここで海賊たちの間には「番号が大きい海賊はそれよりも番号が小さい海賊のお零れをもらうべきだ」という暗黙のことわりがあるため、すべての $ i,j\ (1\ \leq\ i\ \lt\ j\ \leq\ N) $ について $ L_j\ \leq\ L_i $ かつ $ R_i\ \leq\ R_j $ が満たされます。 海賊たちはこの数日、様々な山分けの仕方について考えを巡らせています。そこで、以下の $ Q $ 個のクエリを順に処理してください。 - 海賊 $ l,l+1,\ldots,r $ でお宝を山分けするとき、それぞれがもらうお宝の個数の最小値は最大でいくらになるか。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \hspace{0.5cm}\vdots $ $ L_N $ $ R_N $ $ Q $ $ \text{query}_1 $ $ \text{query}_2 $ $ \hspace{0.4cm}\vdots $ $ \text{query}_Q $ $ i $ 個目のクエリの内容は $ \text{query}_i $ によって表され、その内容は以下の形式で与えられる。 > $ l $ $ r $

$ Q $ 行に渡って出力せよ。$ i\ (1\ \leq\ i\ \leq\ Q) $ 行目には $ i $ 個目のクエリへの答えを出力すること。

### ストーリー 20XX 年、パ研は技術室奥を捨て、海賊となり大海原に漕ぎ出した... ### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ 10^{12}\ (1\ \leq\ i\ \leq\ N) $ - すべての $ i,j\ (1\ \leq\ i\ \lt\ j\ \leq\ N) $ について、$ L_j\ \leq\ L_i $ かつ $ R_i\ \leq\ R_j $ が満たされる - 各クエリにおいて、$ 1\ \leq\ l\ \leq\ r\ \leq\ N $ が満たされる - 入力は全て整数 ### Extra ケース 下記の制約を満たすデータセット（上記の制約を満たす $ 800 $ 点分のテストケースを含む）に正解した場合、追加で $ 1 $ 点が与えられる。ただし、このデータセットにおいては低速な言語による AC が可能であることは保証されない。 - $ 2\ \leq\ N\ \leq\ 5\ \times\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 5\ \times\ 10^5 $ ### Sample Explanation 1 $ 1 $ つ目のクエリにおいては、例えば以下のような山分けの仕方が考えられます。 - 海賊 $ 1 $ にお宝 $ 2,3 $ を、海賊 $ 2 $ にお宝 $ 4,5 $ を割り当てる。 $ 2 $ つ目のクエリにおいては、海賊 $ 2 $ にお宝 $ 1,2,3,4,5 $ の全てを割り当てればよいです。 ### Sample Explanation 2 原案: \[penguinman\](https://atcoder.jp/users/penguinman)