# CSES - Static Range Minimum Queries

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int mxn = 2e5;

struct sprase_table{
    int n;
    vector<vector<long long>> sp;
    sprase_table(vector<int> &x) : n(x.size()){
        sp.resize(20, vector<int>(n));
        for(int i = 0; i<n; i++){
            sp[0][i] = x[i];
        }
        for(int i = 1; i<20; i++){
            for(int j = 0; j + (1 << i) -1 < n; j++){
                sp[i][j] = min(sp[i-1][j], sp[i-1][j+(1 << (i)-1)]);
            }
        }
    }
    int ask(int l, int r){
        int k = __lg(r - l);
        return min(sp[k][l], sp[k][r - (1 << k)]);

    }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin >> n>> q;

    vector<int> x(n+1);

    for(int i  =0; i<n; i++){
        cin >> x[i];
    }
    sprase_table sp(x);

    for(int i  = 0; i<q; i++){
        int a,b;
        cin >> a >> b;
        cout <<sp.ask(a-1,b) << "\n";
    }
    return 0;
}

sp[i][j] 代表什麼？
從 j 開始、長度 2^i 的區間最小值

---

### 特性 1：我們預先算好所有 “長度為 2 的冪次方” 的區間最小值

例如陣列：
[a0, a1, a2, a3, a4, a5, a6, a7]

我們會算：

長度 範例區間 Meaning
* 2^0 = 1 [i] 單點最小值，就是原陣列
* 2^1 = 2 [i, i+2) 兩個一組的最小值
* 2^2 = 4 [i, i+4) 四個一組的最小值
* 2^3 = 8 [i, i+8) 八個一組的最小值

所有這些都在建構階段算好了。

### 特性 2：任意區間都能被「兩段」相同長度的 2^k 區間覆蓋
###
假設查詢 [l, r)
區間長度 = len = r - l
找出最大 k，使得：

2^k ≤ len

然後把查詢區間切成：

**1. [l, l + 2^k)
2. [r - 2^k, r)**

---

DiegoLin --------- 2025/10/24