「Note」单调队列

struct Deque {
	int head, tail, n, m, q[MAXN], a[MAXN], p;
	
	Deque(){}
	Deque(int n, int m, int head, int tail, int p) : n(n), m(m), head(head), tail(tail), p(p){};
	
	int get(int id) {
		int res = a[q[head]];
		while (id - q[head] >= m && head <= tail) head++;
		while (a[id] <= a[q[tail]] && head <= tail) tail--;
		q[++tail] = id;
		return res * p;
	}
	
	void scan() {
		for (int i = 1; i <= n; i++) scanf ("%d", &a[i]), a[i] *= p;
	}
	
}