G - Simultaneous Kagamimochi 2
Source: atcoder
Difficulty: 575

Problem Statement
There are
N
mochi (rice cakes), arranged in ascending order of size.
The size of the
i
-th mochi
(1\leq i\leq N)
is
A_i
.
Given two mochi
A
and
B
, with sizes
a
and
b
respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi
A
on top of mochi
B
if and only if
a
is at most half of
b
.
You are given
Q
integer pairs. Let
(L_i, R_i)
be the
i
-th pair
(1\leq i\leq Q)
, and solve the following problem for each
i
:
Using only the
R_i - L_i + 1
mochi from the
L_i
-th to the
R_i
-th, how many kagamimochi can you make simultaneously?
More precisely, find the maximum non-negative integer
K
such that:
Out of the
R_i - L_i + 1
mochi from the
L_i
-th to the
R_i
-th, choose
2K
mochi and form
K
pairs. For each pair, place one mochi on top of the other, to make
K
kagamimochi.
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 < N)
1 \leq Q \leq 2 \times 10^5
1 \leq L_i < R_i \leq N \ (1 \leq i \leq Q)
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1
A_2
\dotsc
A_N
Q
L_1
R_1
L_2
R_2
\vdots
L_Q
R_Q
Output
Print
Q
lines. The
i
-th line
(1\leq i\leq Q)
should contain the answer to the
i
-th query.
Sample Input 1
11
1 1 2 3 4 4 7 10 11 12 20
5
2 5
3 8
7 11
1 2
1 11
Sample Output 1
2
3
1
0
5
The answers to each query are as follows. One possible way to make the kagamimochi is given for each query.
The mochi sizes are
(1, 2, 3, 4)
. You can make the two kagamimochi
(1,3)
and
(2,4)
.
The mochi sizes are
(2, 3, 4, 4, 7, 10)
. You can make the three kagamimochi
(2,4)
,
(3,7)
, and
(4,10)
.
The mochi sizes are
(7, 10, 11, 12, 20)
. You can make one kagamimochi
(10,20)
.
The mochi sizes are
(1, 1)
. You cannot make any kagamimochi.
The mochi sizes are
(1, 1, 2, 3, 4, 4, 7, 10, 11, 12, 20)
. You can make five kagamimochi
(1,2)
,
(1,3)
,
(4,10)
,
(4,11)
, and
(7,20)
.
Hence, print
2
,
3
,
1
,
0
,
5
in this order.
Sample Input 2
24
127 148 170 174 258 311 331 414 416 436 517 523 532 587 591 638 660 748 760 776 837 857 972 984
15
7 11
8 9
8 13
12 15
9 23
1 17
8 12
1 5
6 17
3 7
12 19
13 18
7 22
1 12
14 15
Sample Output 2
0
0
0
0
2
6
0
1
1
0
0
0
3
5
0

C++ solution:
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 200000;
static const int LOG  = 18;

int N, Q;
long long A[MAXN+5];
int p[MAXN+5], d[MAXN+5];
int st[LOG+1][MAXN+5];
int lg2[MAXN+5];

inline int rmq(int l, int r) {
    // return max_{i=l..r} d[i], or 0 if empty
    if (l > r) return 0;
    int len = r - l + 1;
    int k = lg2[len];
    return max(st[k][l], st[k][r - (1<<k) + 1]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1) read input
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    cin >> Q;
    vector<pair<int,int>> qs(Q);
    for (int i = 0; i < Q; i++) {
        cin >> qs[i].first >> qs[i].second;
        // we'll convert to 0-based later
    }

    // 2) two‐pointer to compute p[i]
    //    p[i] = smallest j>i with A[j] >= 2*A[i], or N if none
    int j = 0;
    for (int i = 0; i < N; i++) {
        j = max(j, i+1);
        while (j < N && A[j] < 2LL * A[i]) 
            j++;
        p[i] = (j < N ? j : N);
    }

    // 3) build the d-array
    //    d[i] = p[i] - i  (>=1), or large if p[i]=N
    for (int i = 0; i < N; i++) {
        if (p[i] == N) 
            d[i] = N+1; 
        else 
            d[i] = p[i] - i;
    }

    // 4) build log‐table for RMQ
    lg2[1] = 0;
    for (int i = 2; i <= N; i++) 
        lg2[i] = lg2[i>>1] + 1;

    // 5) build sparse table on d[]
    for (int i = 0; i < N; i++)
        st[0][i] = d[i];
    for (int k = 1; k <= LOG; k++) {
        int len = 1 << k;
        for (int i = 0; i + len - 1 < N; i++) {
            st[k][i] = max(st[k-1][i], st[k-1][i + (1<<(k-1))]);
        }
    }

    // 6) answer queries
    //    For each [L,R], let m = R-L+1.
    //    Binary‐search minimal D in [ceil(m/2)..m] with
    //       max_{i=L..R-D} d[i] <= D
    //    Then K = m - D.
    for (auto &qr : qs) {
        int L = qr.first - 1;
        int R = qr.second - 1;
        int m = R - L + 1;

        int lo = (m + 1) / 2;  // ceil(m/2)
        int hi = m;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            int right = R - mid;
            // check if sub‐range [L..right] is safe
            if (rmq(L, right) <= mid) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        int D = lo;
        int K = m - D;
        cout << K << "\n";
    }

    return 0;
}

Go solution:
// https://leetcode.cn/problems/find-the-maximum-number-of-marked-indices/description/
// https://atcoder.jp/contests/abc388/tasks/abc388_g

package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int
	fmt.Fscan(in, &n)
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &nums[i])
	}

	var q int
	fmt.Fscan(in, &q)
	M := NewMaxNumOfPair(nums)
	for i := 0; i < q; i++ {
		var start, end int32
		fmt.Fscan(in, &start, &end)
		start--
		fmt.Fprintln(out, M.Query(start, end))
	}
}

type MaxNumOfPair struct {
	n   int32
	seg *SparseTableFast
}

func NewMaxNumOfPair(sortedNums []int) *MaxNumOfPair {
	n := int32(len(sortedNums))
	nexts := make([]int32, n) // !每个元素距离右侧第一个大于等于它两倍的元素的距离.
	ptr := int32(0)
	for i := int32(0); i < n; i++ {
		ptr = max32(ptr, i+1)
		for ptr < n && sortedNums[i]*2 > sortedNums[ptr] {
			ptr++
		}
		nexts[i] = ptr
	}

	seg := NewSparseTableFast(
		n,
		func(i int32) int32 { return nexts[i] - i },
		func() int32 { return 0 },
		func(a, b int32) int32 { return max32(a, b) },
	)
	return &MaxNumOfPair{n: n, seg: seg}
}

func (m *MaxNumOfPair) Query(start, end int32) int32 {
	if start < 0 {
		start = 0
	}
	if end > m.n {
		end = m.n
	}
	if start >= end {
		return 0
	}

	right := MaxRight32(
		0,
		// 能否配k对.
		func(k int32) bool {
			k--
			if 2*k > end-start {
				return false
			}

			maxDist := m.seg.Query(start, start+k)
			return maxDist <= end-start-k
		},
		m.n/2+1,
	)

	return right - 1
}

// RangeMaxWIthIndex

type S = int32

// Static RMQ, O(n)预处理, O(1)查询.
type SparseTableFast struct {
	n        int32
	leaves   []S
	pre, suf []S
	st       *SparseTable
	data     []int32
	e        func() S
	op       func(S, S) S
}

func NewSparseTableFast(n int32, f func(int32) S, e func() S, op func(S, S) S) *SparseTableFast {
	res := &SparseTableFast{}
	bNum := n >> 4
	leaves := make([]S, n)
	for i := int32(0); i < n; i++ {
		leaves[i] = f(i)
	}
	pre, suf := append(leaves[:0:0], leaves...), append(leaves[:0:0], leaves...)
	for i := int32(1); i < n; i++ {
		if i&15 != 0 {
			pre[i] = op(pre[i-1], leaves[i])
		}
	}
	for i := n - 1; i > 0; i-- {
		if i&15 != 0 {
			suf[i-1] = op(leaves[i-1], suf[i])
		}
	}
	st := NewSparseTable(bNum, func(i int32) S { return suf[i<<4] }, e, op)

	// 处理长度小于或等于16的查询
	// 在区间 [i, i+16) 内，如果 i+j 的位置上的值是 [i, i+j] 这个子区间的最小值，那么就将 j-th 位设置为1
	data := make([]int32, n)
	stack := int32(0)
	for i := n - 1; i >= 0; i-- {
		stack = (stack << 1) & 65535
		for stack > 0 {
			k := lowbit(stack)
			tmp := op(leaves[i], leaves[i+k])
			if tmp != leaves[i] {
				break
			}
			stack &= ^(1 << k)
		}
		stack |= 1
		data[i] = stack
	}
	res.n = n
	res.leaves = leaves
	res.pre, res.suf = pre, suf
	res.st = st
	res.data = data
	res.e = e
	res.op = op
	return res
}

func NewSparseTableFastFrom(leaves []S, e func() S, op func(S, S) S) *SparseTableFast {
	return NewSparseTableFast(int32(len(leaves)), func(i int32) S { return leaves[i] }, e, op)
}

func (st *SparseTableFast) Query(start, end int32) S {
	if start >= end {
		return st.e()
	}
	if end-start <= 16 {
		d := st.data[start] & ((1 << (end - start)) - 1)
		return st.leaves[start+topbit(d)]
	}
	end--
	a, b := start>>4, end>>4
	x := st.st.Query(a+1, b)
	x = st.op(st.suf[start], x)
	x = st.op(x, st.pre[end])
	return x
}

// 返回最大的 right 使得 [left,right) 内的值满足 check.
func (ds *SparseTableFast) MaxRight(left int32, check func(e S) bool) int32 {
	if left == ds.n {
		return ds.n
	}
	ok, ng := left, ds.n+1
	for ok+1 < ng {
		mid := (ok + ng) >> 1
		if check(ds.Query(left, mid)) {
			ok = mid
		} else {
			ng = mid
		}
	}
	return ok
}

// 返回最小的 left 使得 [left,right) 内的值满足 check.
func (ds *SparseTableFast) MinLeft(right int32, check func(e S) bool) int32 {
	if right == 0 {
		return 0
	}
	ok, ng := right, int32(-1)
	for ng+1 < ok {
		mid := (ok + ng) >> 1
		if check(ds.Query(mid, right)) {
			ok = mid
		} else {
			ng = mid
		}
	}
	return ok
}

// SparseTable 稀疏表: st[j][i] 表示区间 [i, i+2^j) 的贡献值.
type SparseTable struct {
	st [][]S
	e  func() S
	op func(S, S) S
	n  int32
}

func NewSparseTable(n int32, f func(int32) S, e func() S, op func(S, S) S) *SparseTable {
	res := &SparseTable{}

	b := bits.Len32(uint32(n))
	st := make([][]S, b)
	for i := range st {
		st[i] = make([]S, n)
	}
	for i := int32(0); i < n; i++ {
		st[0][i] = f(i)
	}
	for i := 1; i < b; i++ {
		for j := int32(0); j+(1<<i) <= n; j++ {
			st[i][j] = op(st[i-1][j], st[i-1][j+(1<<(i-1))])
		}
	}
	res.st = st
	res.e = e
	res.op = op
	res.n = n
	return res
}

func NewSparseTableFrom(leaves []S, e func() S, op func(S, S) S) *SparseTable {
	return NewSparseTable(int32(len(leaves)), func(i int32) S { return leaves[i] }, e, op)
}

// 查询区间 [start, end) 的贡献值.
func (st *SparseTable) Query(start, end int32) S {
	if start >= end {
		return st.e()
	}
	b := bits.Len(uint(end-start)) - 1 // log2
	return st.op(st.st[b][start], st.st[b][end-(1<<b)])
}

// 返回最大的 right 使得 [left,right) 内的值满足 check.
func (ds *SparseTable) MaxRight(left int32, check func(e S) bool) int32 {
	if left == ds.n {
		return ds.n
	}
	ok, ng := left, ds.n+1
	for ok+1 < ng {
		mid := (ok + ng) >> 1
		if check(ds.Query(left, mid)) {
			ok = mid
		} else {
			ng = mid
		}
	}
	return ok
}

// 返回最小的 left 使得 [left,right) 内的值满足 check.
func (ds *SparseTable) MinLeft(right int32, check func(e S) bool) int32 {
	if right == 0 {
		return 0
	}
	ok, ng := right, int32(-1)
	for ng+1 < ok {
		mid := (ok + ng) >> 1
		if check(ds.Query(mid, right)) {
			ok = mid
		} else {
			ng = mid
		}
	}
	return ok
}

func topbit(x int32) int32 {
	if x == 0 {
		return -1
	}
	return int32(bits.Len32(uint32(x)) - 1)
}

func lowbit(x int32) int32 {
	if x == 0 {
		return -1
	}
	return int32(bits.TrailingZeros32(uint32(x)))
}

func min32(a, b int32) int32 {
	if a < b {
		return a
	}
	return b
}

func max32(a, b int32) int32 {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 返回最大的 right 使得 [left,right) 内的值满足 check.
// !注意check内的right不包含,使用时需要right-1.
// right<=upper.
func MaxRight32(left int32, check func(right int32) bool, upper int32) int32 {
	ok, ng := left, upper+1
	for ok+1 < ng {
		mid := (ok + ng) >> 1
		if check(mid) {
			ok = mid
		} else {
			ng = mid
		}
	}
	return ok
}

Java solution:
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.function.IntFunction;
import java.util.function.LongFunction;

public class Main {
	public static void main(String[] args) {
		Main o = new Main();
		o.solve();
	}

	public void solve() {
		FastScanner sc = new FastScanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}
		int Q = sc.nextInt();
		int[] L = new int[Q];
		int[] R = new int[Q];
		for (int i = 0; i < Q; i++) {
			L[i] = sc.nextInt() - 1;
			R[i] = sc.nextInt() - 1;
		}

		int[] i0 = new int[N];
		Arrays.fill(i0, -1);
		int[] i1 = new int[N];
		int ii = 0;
		IntMaxSegmentTree tree = new IntMaxSegmentTree(N + 10);
		for (int i = 0; i < N; i++) {
			while ( ii < N && A[ii] < A[i] * 2 ) {
				i0[ii] = i - 1;
				ii++;
			}
			i1[i] = ii;
			tree.update(i, i1[i] - i);
		}

		int[] ans = new int[Q];
		for (int q = 0; q < Q; q++) {
			int _i0 = i0[R[q]];
			int _i1 = i1[L[q]];
			if ( _i0 >= L[q] && _i1 <= R[q] ) {
				ans[q] = R[q] - L[q] + 1 - tree.query(L[q], _i0 + 1);
				ans[q] = Math.min(ans[q], (R[q] - L[q] + 1) / 2);
				ans[q] = Math.min(ans[q], _i0 - L[q] + 1);
			} else {
				ans[q] = 0;
			}
		}
		print(ans, LF);
	}

	static final char LF = '\n';
	static final char SPACE = ' ';
	static final String YES = "Yes";
	static final String NO = "No";
	void print(int[] array, char sep) {
		print(array, sep, n -> n, 0, array.length);
	}
	void print(int[] array, char sep, IntFunction<Integer> conv) {
		print(array, sep, conv, 0, array.length);
	}
	void print(int[] array, char sep, IntFunction<Integer> conv, int start, int end) {
		StringBuilder ans = new StringBuilder();
		for (int i = start; i < end; i++) {
			ans.append(conv.apply(array[i]));
			ans.append(sep);
		}
		ans.deleteCharAt(ans.length() - 1);
		System.out.println(ans.toString());
	}
	void print(long[] array, char sep) {
		print(array, sep, n -> n, 0, array.length);
	}
	void print(long[] array, char sep, LongFunction<Long> conv) {
		print(array, sep, conv, 0, array.length);
	}
	void print(long[] array, char sep, LongFunction<Long> conv, int start, int end) {
		StringBuilder ans = new StringBuilder();
		for (int i = start; i < end; i++) {
			ans.append(conv.apply(array[i]));
			ans.append(sep);
		}
		ans.deleteCharAt(ans.length() - 1);
		System.out.println(ans.toString());
	}
	void printYesNo(boolean yesno) {
		System.out.println(yesno ? YES : NO);
	}
	void printDouble(double val, int digit) {
		System.out.println(String.format("%." + digit + "f", val));
	}
	
	class FastScanner {
		private final InputStream in;
		private final byte[] buf = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;
		FastScanner( InputStream source ) { this.in = source; }
		private boolean hasNextByte() {
			if ( ptr < buflen ) return true;
			else {
				ptr = 0;
				try { buflen = in.read(buf); } catch (IOException e) { e.printStackTrace(); }
				if ( buflen <= 0 ) return false;
			}
			return true;
		} 
		private int readByte() { if ( hasNextByte() ) return buf[ptr++]; else return -1; } 
		private boolean isPrintableChar( int c ) { return 33 <= c && c <= 126; }
		private boolean isNumeric( int c ) { return '0' <= c && c <= '9'; }
		private void skipToNextPrintableChar() { while ( hasNextByte() && !isPrintableChar(buf[ptr]) ) ptr++; }
		public boolean hasNext() { skipToNextPrintableChar(); return hasNextByte(); }
		public String next() {
			if ( !hasNext() ) throw new NoSuchElementException();
			StringBuilder ret = new StringBuilder();
			int b = readByte();
			while ( isPrintableChar(b) ) { ret.appendCodePoint(b); b = readByte(); }
			return ret.toString();
		}
		public long nextLong() {
			if ( !hasNext() ) throw new NoSuchElementException();
			long ret = 0;
			int b = readByte();
			boolean negative = false;
			if ( b == '-' ) { negative = true; if ( hasNextByte() ) b = readByte(); }
			if ( !isNumeric(b) ) throw new NumberFormatException();
			while ( true ) {
				if ( isNumeric(b) ) ret = ret * 10 + b - '0';
				else if ( b == -1 || !isPrintableChar(b) ) return negative ? -ret : ret;
				else throw new NumberFormatException();
				b = readByte();
			}
		}
		public int nextInt() { return (int)nextLong(); }
		public double nextDouble() { return Double.parseDouble(next()); }
	}
}
class IntSegmentTree {
  // 最下段の個数
  int N = 1;
  int[] tree = null;

  // 演算に影響しない値(加減なら0、最大なら-INF等)
  // f(a, e) = f(e, a) = f(a)となるようなe
  int IDENTITY = 0;

  // 演算
  int f(int a, int b) {
    return a + b;
  }
  int identity() {
    return IDENTITY;
  }

  // 要素1〜maxまで
  IntSegmentTree(int max) {
    while ( N <= max ) {
      N *= 2;
    }
    
    tree = new int[2 * N - 1];
    Arrays.fill(tree, identity());
  }

  // 初期化
  void init(int[] arr) {
    System.arraycopy(arr, 0, tree, N - 1, arr.length);

    // 演算実行
    for ( int i = N - 2 ; i >= 0 ; i-- ) {
      tree[i] = f(tree[2 * i + 1], tree[2 * i + 2]);
    }
  }

  // i番目(0-indexed)の値
  int get(int i) {
    return tree[N - 1 + i];
  }

  // i番目の要素をaに更新
  void update(int i, int a) {
    int idx = N - 1 + i;
    tree[idx] = a;
    while ( idx > 0 ) {
      idx = (idx - 1) / 2;
      tree[idx] = f(tree[2 * idx + 1], tree[2 * idx + 2]);
    }
  }

  // [i, j)の区間(i番目(含む)からj番目(含まない))までの間で演算実行
  int query(int i, int j) {
    return query(i, j, 0, 0, N);
  }
  int query(int i, int j, int cur, int l, int r) {
    // 入っていない場合
    if ( r <= i || j <= l ) {
      return identity();
    }
    // 完全に入っている場合
    if ( i <= l && r <= j ) {
      return tree[cur];
    }

    int val0 = query(i, j, 2 * cur + 1, l, (l + r) / 2);
    int val1 = query(i, j, 2 * cur + 2, (l + r) / 2, r);
    return f(val0, val1);
  }
}

class IntSumSegmentTree extends IntSegmentTree {
  @Override
  int f(int a, int b) {
    return a + b;
  }
  @Override
  int identity() {
    return 0;
  }
  IntSumSegmentTree(int max) {
    super(max);
  }
}

class IntMinSegmentTree extends IntSegmentTree {
  @Override
  int f(int a, int b) {
    return Math.min(a, b);
  }
  @Override
  int identity() {
    return Integer.MAX_VALUE;
  }
  IntMinSegmentTree(int max) {
    super(max);
  }
}

class IntMaxSegmentTree extends IntSegmentTree {
  @Override
  int f(int a, int b) {
    return Math.max(a, b);
  }
  @Override
  int identity() {
    return Integer.MIN_VALUE;
  }
  IntMaxSegmentTree(int max) {
    super(max);
  }
}

JavaScript solution:
var fs = require("fs");
// https://gist.github.com/simonlindholm/38e1a3ff5d99fdbceda541f112f9daf3
var Kattio = {
    _buf: Buffer.alloc(1 << 14),
    _bufPos: 0,
    _bufLen: 0,
    _ensure: function() {
        if (this._bufPos === this._bufLen) {
            this._bufPos = 0;
            this._bufLen = fs.readSync(0, this._buf, 0, this._buf.length, null);
        }
    },
    _isws: function(ch) {
        return ch === 32 || ch === 9 || ch === 10 || ch === 13;
    },
    _islf: function(ch) {
        return ch === 10 || ch === 13;
    },
    _peekChar: function() {
        this._ensure();
        return this._bufPos === this._bufLen ? 0 : this._buf[this._bufPos];
    },
    _skipWs: function() {
        while (this._isws(this._peekChar()))
            this._bufPos++;
    },
    _readUntil: function(stop) {
        this._ensure();
        if (this._bufPos === this._bufLen)
            throw new Error("eof");
        var start = this._bufPos;
        var before = null;
        for (;;) {
            if (this._bufPos === this._bufLen) {
                // Hit the end; need to switch buffers. Thus, stash away all we have so far
                // into the 'before' buffer.
                var len = this._bufPos - start, preLen = (before ? before.length : 0);
                var nbuf = Buffer.alloc(len + preLen);
                if (before)
                    before.copy(nbuf);
                before = nbuf;
                this._buf.copy(before, preLen, start);
                this._ensure();
                start = this._bufPos;
            }
            if (this._bufPos === this._bufLen || stop(this._buf[this._bufPos])) break;
            this._bufPos++;
        }
        if (!before)
            return this._buf.toString("utf8", start, this._bufPos);
        var after = this._buf.slice(start, this._bufPos);
        var res = Buffer.alloc(before.length + after.length);
        before.copy(res);
        after.copy(res, before.length);
        return res.toString();
    },

    nextToken: function() {
        this._skipWs();
        return this._readUntil(this._isws);
    },

    nextLine: function() {
        var line = this._readUntil(this._islf);
        if (this._peekChar() === 13) this._bufPos++;
        if (this._peekChar() === 10) this._bufPos++;
        return line;
    },

    nextNumber: function() { return +this.nextToken(); },
    nextInt: function() { return this.nextToken()|0; }
};

let t = 1
// t = Kattio.nextNumber()
while (t--) console.log(solve())

function solve() {
    const n = Kattio.nextNumber()
    const arr = Array(n)
    let j = -1
    const ls = Array(n)
    for (let i = 0; i < n; i++) {
        arr[i] = Kattio.nextNumber()
        while (j + 1 < n && arr[j + 1] * 2 <= arr[i]) j++
        ls[i] = j - i
    }
    // console.log(ls)
    const log = Math.ceil(Math.log2(n))
    const dp = Array(log + 1).fill(0).map(() => Array(n))
    for (let j = 0; j <= log; j++) {
        for (let i = 0; i < n; i++) {
            if (j) {
                const k = i + (1 << (j - 1))
                dp[j][i] = Math.min(dp[j - 1][i], k < n ? dp[j - 1][k] : Infinity)
            } else {
                dp[j][i] = ls[i]
            }
        }
    }
    // console.log(dp)
    // for (let i = 0; i < n; i++) {
    //     for (let j = i; j < n; j++) {
    //         cal(i, j)
    //     }
    // }
    // cal(3, 7)
    // console.log(ls)
    // return
    //
    const q = Kattio.nextNumber()
    const ans = Array(q)
    for (let i = 0; i < q; i++) {
        const l = Kattio.nextNumber() - 1
        const r = Kattio.nextNumber() - 1
        // console.log([l, r])
        ans[i] = cal(l, r)
    }
    return ans.join('\n')

    function cal(l, r) {
        const len = r - l + 1
        const a = binarySearch(1, Math.floor(len / 2), k => {
            const p = Math.floor(Math.log2(k))
            const min = Math.min(dp[p][r - k + 1], dp[p][r - (1 << p) + 1])
            // console.log([k, min], l - (r - k + 1))
            return min >= l - (r - k + 1)
            // for (let j = 0; j <= log; j++) {
            //     if (l + (1 << j) - 1 >= r) {
            //         if (j) j--
            //         return Math.min(dp[j][l], dp[j][r - (1 << j) + 1])
            //             >= l - (r - k + 1)
            //     }
            // }
            // [l, l + k - 1]
            // [r - k + 1, r]
            // return min(ls[x]) >= r - k + 1
        })
        // const b = binarySearch(1, Math.floor(len / 2), k => {
        //     for (let i = 0; i < k; i++) {
        //         // console.log(k, i, [ls[r - k + 1 + i], l + i])
        //         // if (ls[r - k + 1 + i] < l + i) return 0
        //         if (ls[r - k + 1 + i]
        //             // - (r - k + 1 + i)
        //             + (r - k + 1) < l) return 0
        //     }
        //     return 1
        // })
        // if (a !== b) console.log([l, r], [a, b])
        return a
    }
}
function binarySearch(l, r, fn) {
    while (l <= r) {
        const m = Math.floor((l + r) / 2)
        if (fn(m)) {
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return r
}

Python solution:
from sys import stdin, stdout
import bisect

# --- Precomputation of next pointers and sparse table for RMQ on array G ---
# A is sorted in non–decreasing order.
# For each index i, we define next[i] to be the smallest j>i such that A[j] >= 2*A[i].
# If no such j exists, we set next[i] = N.
# Then we define G[i] = next[i] - i.
#
# In any query [L,R] (0-indexed) the maximum number of valid kagamimochi pairs
# (each pair being a top mochi A[i] and a bottom mochi A[j] with 2*A[i] <= A[j])
# is given by the maximum integer k (with 1 <= k <= (R-L+1)//2) such that
#
#     b_{k-1} = L + (k-1) + max( half, max{ G[x] for x in [L, L+k-1] } )  <= R,
#
# where half = (R-L+1)//2 and D = R-L.
#
# Equivalently, letting f(k) = (k-1) + max( half, RMQ_G(L, L+k-1) ),
# we require f(k) <= (R-L) = D.
#
# Since f(k) is non–decreasing in k, we can binary search for the maximum k
# satisfying f(k) <= D.
#
# The sparse table built on G (of length N) allows RMQ (range maximum query)
# on any interval in O(1) time.

# Read input using sys.stdin.readline (do not use sys.stdin.read)
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))

# Compute next pointer for each index.
next_arr = [0] * N
for i in range(N):
    j = bisect.bisect_left(A, 2 * A[i], i + 1, N)
    next_arr[i] = j if j < N else N

# Compute G[i] = next_arr[i] - i.
G = [next_arr[i] - i for i in range(N)]

# Build sparse table for RMQ on G.
# st[k][i] will hold max(G[i], ..., G[i + 2^k - 1]).
log_table = [0] * (N + 1)
for i in range(2, N + 1):
    log_table[i] = log_table[i >> 1] + 1
K = log_table[N] + 1
st = [G[:]]
k = 1
while (1 << k) <= N:
    prev = st[k - 1]
    size = N - (1 << k) + 1
    cur = [0] * size
    step = 1 << (k - 1)
    for i in range(size):
        a = prev[i]
        b = prev[i + step]
        cur[i] = a if a >= b else b
    st.append(cur)
    k += 1

def query_max(l, r):
    # Returns max(G[l..r])
    length = r - l + 1
    j = log_table[length]
    a = st[j][l]
    b = st[j][r - (1 << j) + 1]
    return a if a >= b else b

# --- Process queries ---
# For a given query [L,R] (converted to 0-indexed),
# let m = R-L+1, D = R-L, and half = m//2.
# The maximum possible number of pairs is k_max = m//2.
#
# For any candidate k (1 <= k <= k_max), define
#    f(k) = (k-1) + max( half, max{ G[x] for x in x in [L, L+k-1] } ).
#
# The pairing using the first k mochi (as tops) is valid if f(k) <= D.
# We binary–search for the maximum k with f(k) <= D.
#
# (If no k >= 1 works then answer is 0.)

Q = int(input())
out_lines = []
for _ in range(Q):
    s = input()
    if not s:
        break
    L_str, R_str = s.split()
    L = int(L_str) - 1
    R = int(R_str) - 1
    m = R - L + 1
    D = R - L
    half = m >> 1  # m//2
    k_max = m >> 1  # maximum possible pairs
    if k_max < 1:
        out_lines.append("0")
        continue
    lo = 1
    hi = k_max + 1  # hi is exclusive
    while lo < hi:
        mid = (lo + hi) >> 1
        # Query maximum of G in interval [L, L+mid-1]
        cur_max = query_max(L, L + mid - 1)
        # f(mid) = (mid-1) + max(half, cur_max)
        fmid = (mid - 1) + (half if half >= cur_max else cur_max)
        if fmid <= D:
            lo = mid + 1
        else:
            hi = mid
    ans = lo - 1
    out_lines.append(str(ans))
    
stdout.write("\n".join(out_lines))

Ruby solution:
(N,),A,(Q,),*Qry = $<.map{|ln| ln.split.map(&:to_i) }
Qry.map!{|l,r| [l-1,r-1] }

P = A.map{|a|
	A.bsearch_index{|b| a+a<=b }||N
}
PP = 17.times.inject([P]){|pp,w|
	ps,w = pp[-1],1<<w
	pp<<N.times.map.with_index(w){|i,j|
		pi = [ps[i],j+w+w-1].max
		pj = [ps[j]||N,pi+w].max
		[pj,N].min
	}
}

puts Qry.map{|l,r|
	lp = i = l
	PP.each_with_index.reverse_each{|ps,wr|
		wl,wr = i-l,1<<wr
		ip = [lp,i+wr+wl-1].max
		ip = [ip+wr,ps[i]].max
		lp,i = ip,i+wr if ip<=r
	}
	next i-l
}