1
const int N = 1e6+5;
2
int n, k;
3
int a[N];
4
deque<int> q;
5
signed main(){
6
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
7
    cin >> n >> k;
8
    for(int i = 1; i <= n; i++){
9
        cin >> a[i];
10
    }
11
    for(int i = 1; i <= n; i++){
12
        while(!q.empty() && a[q.back()] >= a[i]) q.pop_back();
13
        q.push_back(i);
14
        if(i >= k){
15
            while(q.front() <= i - k) q.pop_front();
16
            cout << a[q.front()] << " ";
17
        }
18
    }
19
    cout << endl;
20
    while(!q.empty()) q.pop_front();
21
    for(int i = 1; i <= n; i++){
22
        while(!q.empty() && a[q.back()] <= a[i]) q.pop_back();
23
        q.push_back(i);
24
        if(i >= k){
25
            while(q.front() <= i - k) q.pop_front();
26
            cout << a[q.front()] << " ";
27
        }
28
    }
29
    return 0;
30
}