1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <cmath> 6 # include <vector> 7 # include <map> 8 # include <queue> 9 # include <cstdlib>10 # define MAXN 100000111 using namespace std;12 13 inline int get_num() {14     int k = 0, f = 1;15     char c = getchar();16     for(; !isdigit(c); c = getchar()) if(c == ‘-‘) f = -1;17     for(; isdigit(c); c = getchar()) k = k * 10 + c - ‘0‘;18     return k * f;19 }20 21 int n, k, h1 = 1, t1, h2 = 1, t2;22 int a[MAXN], q1[MAXN], q2[MAXN], ans1[MAXN], ans2[MAXN];23 24 int main()25 {26     int i;27     n = get_num();28     k = get_num();29     for(i = 1; i <= n; i++) a[i] = get_num();30     for(i = 1; i <= n; i++)31     {32         while(h1 <= t1 && q1[h1] < i - k + 1) h1++;33         while(h2 <= t2 && q2[h2] < i - k + 1) h2++;34         while(h1 <= t1 && a[q1[t1]] > a[i]) t1--;35         q1[++t1] = i;36         while(h2 <= t2 && a[q2[t2]] < a[i]) t2--;37         q2[++t2] = i;38         ans1[i] = a[q1[h1]];39         ans2[i] = a[q2[h2]];40     }41     for(i = k; i <= n; i++) printf("%d ", ans1[i]);42     puts("");43     for(i = k; i <= n; i++) printf("%d ", ans2[i]);44     puts("");45     return 0;46 }