AT_pakencamp_2024_day2_d Double Mochi

パケン国には、年の初めに縦に餅を重ねた縁起物「ダブル餅」を飾る風習があります。このダブル餅は次の性質を持ちます。 - 上から順に重ねた餅の重さをそれぞれ $ V_1, V_2, \dots, V_n $ （餅の個数を $ n $ とする）としたとき、すべての $ i $ ( $ 1 \leq i \leq n-1 $ ) に対して $ 2 \times V_i \leq V_{i+1} $ が成り立つ。 パケン国の住民であるパケ子さんは $ 1 $ から $ N $ までの番号が付いた $ N $ 個の餅を持っています。餅 $ i $ ( $ 1 \leq i \leq N $ ) の重さは $ W_i $ です。 ここで、全ての $ i $ ( $ 1 \leq i \leq N-1 $ ) について $ W_i \leq W_{i+1} $ が成り立ちます。 パケ子さんはあなたに $ Q $ 個の問い合わせをします。 $ i $ 番目の問い合わせは、「 $ L_i $ 番から $ R_i $ 番の番号が付いた餅全てをちょうど 1 つずつ使っていくつかのダブル餅を作るとき、最小でいくつのダブル餅を作ることになるか？」という内容です。それぞれに対して求める最小個数を回答してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ W_1 $ $ W_2 $ $ \ldots $ $ W_N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目の問い合わせに対する答えを出力せよ。

### 小課題 1. ( $ 1 $ 点) $ N \leq 6 $ , $ Q = 1 $ 2. ( $ 4 $ 点) $ N \leq 16 $ , $ Q = 1 $ 3. ( $ 10 $ 点) $ N \leq 2000 $ , $ Q = 1 $ 4. ( $ 10 $ 点) $ Q = 1 $ 5. ( $ 75 $ 点) 追加の制約はない ### Sample Explanation 1 $ 1 $ 番目の問い合わせでは、使う餅の重さはそれぞれ $ 3,4,6,8,16 $ です。 - 重さが $ 3 $ と $ 6 $ の餅 を使ったダブル餅 - 重さが $ 4,8,16 $ の餅 を使ったダブル餅 このように $ 2 $ つのダブル餅を作ることで、作るダブル餅の個数は $ 2 $ 個 となり、これが最小です。 $ 2 $ 番目の問い合わせでは、使う餅の重さは $ 3 $ のみです。この場合、作るダブル餅の個数は必ず $ 1 $ 個 になります。 餅が $ 1 $ つだけでも、それ自体でダブル餅として扱うことに注意してください。 $ 3 $ 番目の問い合わせでは、使う餅の重さはそれぞれ $ 2,3,3,4,6,8,16 $ です。 - 重さが $ 3 $ と $ 6 $ の餅 を使ったダブル餅 - 重さが $ 2,4,8,16 $ の餅 を使ったダブル餅 - 重さが $ 3 $ の餅単体 で構成されるダブル餅 このように $ 3 $ 個のダブル餅 を作ることで、作るダブル餅の個数は $ 3 $ 個 となり、これが最小です。 このサンプルは小課題 $ 5 $ の制約を満たします。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq W_i \leq 10^9 $ ( $ 1 \leq i \leq N $ ) - $ 1 \leq L_i \leq R_i \leq N $ ( $ 1 \leq i \leq Q $ ) - $ W_i \leq W_{i+1} $ ( $ 1 \leq i \leq N-1 $ ) - 入力は全て整数