AT_abc388_g [ABC388G] Simultaneous Kagamimochi 2

[problemUrl]: https://atcoder.jp/contests/abc388/tasks/abc388_g $ N $ 個の餅が小さいほうから順に並んでいます。 $ i $ 番目 $ (1\leq\ i\leq\ N) $ の餅の大きさは $ A\ _\ i $ です。 $ 2 $ つの餅 $ A,B $ の大きさをそれぞれ $ a,b $ としたとき、$ a $ が $ b $ の半分以下であるとき、かつそのときに限り、餅 $ A $ を餅 $ B $ の上に乗せて鏡餅を $ 1 $ つ作ることができます。 整数の $ 2 $ つ組が $ Q $ 個与えられます。 $ i $ 番目 $ (1\leq\ i\leq\ Q) $ の $ 2 $ つ組を $ (L\ _\ i,R\ _\ i) $ として、次の問題をすべての $ i $ について解いてください。 > $ L\ _\ i $ 番目から $ R\ _\ i $ 番目までの $ R\ _\ i-L\ _\ i+1 $ 個の餅だけを使って、同時にいくつの鏡餅を作ることができるか求めてください。 > > より厳密には、以下ができるような最大の非負整数 $ K $ を求めてください。 > > - $ L\ _\ i $ 番目から $ R\ _\ i $ 番目までの $ R\ _\ i-L\ _\ i+1 $ 個の餅から $ 2K $ 個の餅を選んで $ K $ 個の $ 2 $ つ組に分け、それぞれの組について一方をもう一方の上に乗せることで鏡餅を $ K $ 個作る。

N/A

N/A

### 制約 - $ 2\leq\ N\leq\ 2\times\ 10\ ^\ 5 $ - $ 1\leq\ A\ _\ i\leq\ 10\ ^\ 9\ (1\leq\ i\leq\ N) $ - $ A\ _\ i\leq\ A\ _\ {i+1}\ (1\leq\ i\lt\ N) $ - $ 1\leq\ Q\leq\ 2\times\ 10\ ^\ 5 $ - $ 1\leq\ L\ _\ i\lt\ R\ _\ i\leq\ N\ (1\leq\ i\leq\ Q) $ - 入力はすべて整数 ### Sample Explanation 1 それぞれの問題に対する答えは以下のようになります。 鏡餅の作り方は一例です。 - それぞれの餅の大きさは $ (1,2,3,4) $ です。$ (1,3),(2,4) $ の $ 2 $ つの鏡餅を作ることができます。 - それぞれの餅の大きさは $ (2,3,4,4,7,10) $ です。$ (2,4),(3,7),(4,10) $ の $ 3 $ つの鏡餅を作ることができます。 - それぞれの餅の大きさは $ (7,10,11,12,20) $ です。$ (10,20) $ の $ 1 $ つの鏡餅を作ることができます。 - それぞれの餅の大きさは $ (1,1) $ です。$ 1 $ つも鏡餅を作ることができません。 - それぞれの餅の大きさは $ (1,1,2,3,4,4,7,10,11,12,20) $ です。$ (1,2),(1,3),(4,10),(4,11),(7,20) $ の $ 5 $ つの鏡餅を作ることができます。 以上より、`2` `3` `1` `0` `5` をこの順に出力してください。