#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e6 + 9;
int n, k;
int a[MAXN], ans1[MAXN], ans2[MAXN];

signed main() {
	//freopen("P1886_4.in", "r", stdin);
	cin>>n>>k;
	int mv1, ef1 = 0;
	int mv2, ef2 = 0;
	for (int i = 1; i <= n; i++) {
		cin>>a[i];
		if (ef1 == 0) {
			mv1 = a[i];
			ef1 = k;
		} else if (a[i] >= mv1) {
			mv1 = a[i];
			ef1 = k;
		}
		ef1--;
		ans1[i] = mv1;
		if (ef2 == 0) {
			mv2 = a[i];
			ef2 = k;
		} else if (a[i] <= mv2) {
			mv2 = a[i];
			ef2 = k;
		}
		ef2--;
		ans2[i] = mv2;
	}
	ef1 = 0;
	ef2 = 0;
	for (int i = n + k - 1; i > 0; i--) {
		if (ef1 == 0) {
			mv1 = a[i];
			ef1 = k;
		} else if (a[i] >= mv1) {
			mv1 = a[i];
			ef1 = k;
		}
		ef1--;
		ans1[i + k - 1] = max(mv1, ans1[i + k - 1]);
		if (ef2 == 0) {
			mv2 = a[i];
			ef2 = k;
		} else if (a[i] <= mv2) {
			mv2 = a[i];
			ef2 = k;
		}
		ef2--;
		ans2[i + k - 1] = min(mv2, ans2[i + k - 1]);
	}
	for (int i = k; i <= n; i++) {
		cout << ans2[i] << " ";
	}
	cout << endl;
	for (int i = k; i <= n; i++) {
		cout << ans1[i] << " ";
	}
	return 0;
}

思路如下： 以计算区间最大值为例，由题可知序列中某个元素a[i]，可能影响到长为k的一段答案，而当且仅当该元素前k-1个元素中存在更大值或后k-1个元素中存在更大值时，a[i]能影响到的某段答案将会被该更大值覆盖。

因此可以分两次从前向后枚举每个元素向后的影响以及从后向前枚举每个元素向前的影响，当目前的元素大于等于临时最大值（mv）或影响区间结束（ef=0）时，更新临时最大值为当前元素值并重置其影响范围。此后若答案小于临时最大值则把答案更新为临时最大值

感觉想出来了O(n)的做法就不太对劲，然而自己想了好久没想通为什么不对，求求各位大佬帮解惑一下了orz