AT_abc388_g.[ABC388G] Simultaneous Kagamimochi 2

有 $N$ 个饼从小到大依次排列。第 $i$ 个饼（$1 \leq i \leq N$）的大小为 $A_i$。

对于两个饼 $A$ 和 $B$，其大小分别为 $a$ 和 $b$，当且仅当 $a$ 不超过 $b$ 的一半时，可以将饼 $A$ 放在饼 $B$ 上，形成一个镜饼。

给定 $Q$ 个整数对。第 $i$ 个整数对为 $(L_i, R_i)$，请对每个 $i$ 解决以下问题：

仅使用第 $L_i$ 到第 $R_i$ 个饼（共 $R_i - L_i + 1$ 个饼），最多可以同时制作多少个镜饼？

更严格地说，求最大的非负整数 $K$，使得：

• 从第 $L_i$ 到第 $R_i$ 个饼中选出 $2K$ 个饼，将其分成 $K$ 对，每对中一个饼放在另一个饼上，形成 $K$ 个镜饼。

输入通过标准输入给出，格式如下：

$N$
$A_1$ $A_2$ $\dots$ $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 \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 < N$）
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq L_i < R_i \leq N$（$1 \leq i \leq Q$）
• 输入均为整数

样例解释 1

每个问题的答案如下所示。镜饼的制作方式为示例：

• 饼的大小为 $(1,2,3,4)$。可以制作 $(1,3)$ 和 $(2,4)$ 两个镜饼。
• 饼的大小为 $(2,3,4,4,7,10)$。可以制作 $(2,4)$、$(3,7)$ 和 $(4,10)$ 三个镜饼。
• 饼的大小为 $(7,10,11,12,20)$。可以制作 $(10,20)$ 一个镜饼。
• 饼的大小为 $(1,1)$。无法制作任何镜饼。
• 饼的大小为 $(1,1,2,3,4,4,7,10,11,12,20)$。可以制作 $(1,2)$、$(1,3)$、$(4,10)$、$(4,11)$ 和 $(7,20)$ 五个镜饼。

因此，请按顺序输出 2、3、1、0、5。