1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17

class sparse_table {
private: int st[20][100000];
public:
	int log(int x) { return 32 - __builtin_clz(x) - 1; }

	sparse_table(int N, int A[]) {
		for (int i = 0; i < N; i++) st[i][0] = A[i];
		for (int i = 0; i <= log(N); i++) {
			for (int j = 0; j + (1 << i) < N; j++) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
		}
	}

	int query(int i, int j) {
		int k = log(j - i + 1);
		return min(st[k][i], st[k][j - (1 << k) + 1]);
	}
};