本来想手动写一个双端队列玩玩，然后用几个题目测试一下，结果过不去。

using namespace std;
template <typename new_dype>
class Deque{
	struct De_node{
		new_dype val;
		De_node *next = NULL, *prev = NULL;
	}*tail, *head;
public:
	Deque():tail(NULL), head(NULL){
		return;
	}
	void pop_back(){
		if(tail){
			De_node *temp = tail;
			tail = tail->prev;
			if(tail)
				tail->next = NULL;
			delete temp;
		}
	}
	void pop_front(){
		if(head){
			De_node *temp = head;
			head = head->next;
			if(head)
				head->prev = NULL;
			delete temp;
		}
	}
	void push_back(new_dype num){
		De_node *newt = new De_node();
		newt->val = num;
		if(tail){
			tail->next = newt;
			newt->prev = tail;
		}else{
			newt->prev = NULL;
		}
		if(!head) head = newt;
		tail = newt;
	}
	void push_front(new_dype num){
		De_node *newt = new De_node();
		newt->val = num;
		if(head){
			newt->next = head;
			head->prev = newt;
		}else{
			newt->next = NULL;
		}
		if(!tail) tail = newt;
		head = newt;
	}
	new_dype front(){
		if(head)
			return head->val;
	}
	new_dype back(){
		if(tail)
			return tail->val;
	}
	void clear(){
		while(head){
			De_node *temp = head;
			head = head->next;
			delete temp;
		}
		tail = NULL;
	}
	bool empty(){
		return !(tail && head);
	}
};
int n, k;
struct node{
	int id, num;
}a[1000010];
Deque<node>q;
int main(){
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> a[i].num;
		a[i].id = i;
	}
	for(int i = 1; i <= n; i++){//最小值 
		while(!q.empty() && a[i].num < q.back().num){
			q.pop_back();
		}
		q.push_back(a[i]);
		while(i - q.front().id >= k){
			q.pop_front();
		}
		if(i >= k){
			cout << q.front().num << " ";
		}
	}
	q.clear();
	cout << endl;
	for(int i = 1; i <= n; i++){//最大值 
		while(!q.empty() && a[i].num > q.back().num){
			q.pop_back();
		}
		q.push_back(a[i]);
		while(i - q.front().id >= k){
			q.pop_front();
		}
		if(i >= k){
			cout << q.front().num << " ";
		}
	}
	return 0;
}