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$ 个镜饼。

无

无

- $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`。