原理：判断输入の这一个数据能否进入。

//单调栈笔记&C++竞赛团队训练17047
#include<bits/stdc++.h>

using namespace std;
int stk[123456],tt;/*top，顶部*/

int main(){
	int n;
	cin>>n;
	while(n--){
		int temp;
		cin>>temp;
		//temp>栈顶符合（保证栈不为空）
		while(tt&&stk[tt]>=temp)tt--;
		//stk[tt]就是答案
		if(!tt)cout<<-1<<' ';
		else cout<<stk[tt]<<' ';
		stk[++tt]=temp;
	}
	
	
	return 0;
}

//单调队列笔记&C++竞赛团队训练2120
#include<bits/stdc++.h>

using namespace std;
int a[1234567],q[1234567];

int main() {
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	
	//head,tail
	int hh=0,tt=-1;
	for(int i=0;i<n;i++){
		//增加元素
		if(hh<tt&&i-k+1>q[hh])hh++;
		
		while(hh<=tt&&a[q[tt]]>=a[i])tt--;
		
		q[++tt]=i;
		
		if(i>=k-1){
			printf("%d ",a[q[hh]]);
		}
	}
	
	cout<<endl;
	
	hh=0,tt=-1;
	for(int i=0;i<n;i++){
		//增加元素
		if(hh<tt&&i-k+1>q[hh])hh++;
		
		while(hh<=tt&&a[q[tt]]<=a[i])tt--;
		
		q[++tt]=i;
		
		if(i>=k-1){
			printf("%d ",a[q[hh]]);
		}
	}
	
	return 0;
}