問題文

パケン国には、年の初めに縦に餅を重ねた縁起物「ダブル餅」を飾る風習があります。このダブル餅は次の性質を持ちます。

• 上から順に重ねた餅の重さをそれぞれ 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 つずつ使っていくつかのダブル餅を作るとき、最小でいくつのダブル餅を作ることになるか？」という内容です。それぞれに対して求める最小個数を回答してください。

制約

• 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)
• 入力は全て整数

小課題

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 点) 追加の制約はない

入力例 1

7 3
2 3 3 4 6 8 16
3 7
2 2
1 7

出力例 1

2
1
3

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 の制約を満たします。