AT_abc388_g [ABC388G] Simultaneous Kagamimochi 2

$ 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 _ 1 $ $ A _ 2 $ $ \dotsc $ $ A _ N $ $ Q $ $ L _ 1 $ $ R _ 1 $ $ L _ 2 $ $ R _ 2 $ $ \vdots $ $ L _ Q $ $ R _ Q $

$ Q $ 行出力せよ。 $ i $ 行目 $ (1\leq i\leq Q) $ には、 $ i $ 番目の $ 2 $ つ組に対応する問題の答えを出力せよ。

### 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` をこの順に出力してください。 ### Constraints - $ 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) $ - 入力はすべて整数