RE on #8#9

#include <bits/stdc++.h>
#define int long long
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin), p1 == p2) ? EOF : *p1++)
using namespace std;
char *p1, *p2, buf[10000001];

int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		f = ch == '-' ? -1 : 1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		res = (res << 1) + (res << 3) + (ch ^ 48);
		ch = getchar();
	}
	return res * f;
}

const int inf = (int)numeric_limits<int>::max() >> 1;
const int ninf = (int)numeric_limits<int>::min() >> 1;
int n, k, head, tail, q[4000005];
pair<int, int> a[1000005];

void prepare() {
	n = read(), k = read();
	for (int i = 1; i <= n; i++) {
		a[i].first = read(), a[i].second = i;
	}
}

void solve() {
	q[head = tail = 1] = 0;
	for (int i = 1; i <= n; i++) {
		while (head <= tail && a[i].first <= a[q[head]].first) {
			head++;
		}
		q[--head] = a[i].second;
		while (head <= tail && q[tail] <= i - k) {
			tail--;
		}
		if (i >= k) {
			printf ("%lld ", a[q[tail]].first);
		}
	}
	putchar('\n');
	q[head = tail = 1] = 0;
	for (int i = 1; i <= n; i++) {
		while (head <= tail && a[i].first >= a[q[head]].first) {
			head++;
		}
		q[--head] = a[i].second;
		while (head <= tail && q[tail] <= i - k) {
			tail--;
		}
		if (i >= k) {
			printf ("%lld ", a[q[tail]].first);
		}
	}
}

void work() {
	prepare(), solve();
}

signed main() {
	work();
	return 0;
}