1 #include <cstdio>
2 #include <cstring>
3 #define N 1000005
4
5 struct Que
6 {
7 int i, x; //x为加入序号
8 }q1[N],q2[N];
9 int front1, front2, tail1, tail2;
10 int minx[N], maxx[N], n, k;
11
12 //递增找最小
13 void add1(int i, int x)
14 {
15 while(front1<=tail1)
16 {
17 if(i < q1[tail1].i+k && q1[tail1].x < x)
18 break;
19 tail1--;
20 }
21 q1[++tail1].x = x;
22 q1[tail1].i = i;
23 }
24
25 //递减找最大
26 void add2(int i, int x)
27 {
28 while(front2<=tail2)
29 {
30 if(i < q2[tail2].i+k && q2[tail2].x > x)
31 break;
32 tail2--;
33 }
34 q2[++tail2].x = x;
35 q2[tail2].i = i;
36 }
37
38 int query1(int i)
39 {
40 while(front1<=tail1 && i >= q1[front1].i+k)
41 front1++;
42 return q1[front1].x;
43 }
44
45 int query2(int i)
46 {
47 while(front2<=tail2 && i >= q2[front2].i+k)
48 front2++;
49 return q2[front2].x;
50 }
51
52 int main()
53 {
54 while(scanf("%d%d",&n,&k)!=EOF)
55 {
56 front1 = 0; tail1 = -1;
57 front2 = 0; tail2 = -1;
58 int x;
59 for(int i=1; i<=k-1; i++)
60 {
61 scanf("%d",&x);
62 add1(i, x);
63 add2(i, x);
64 }
65 for(int i=k; i<=n; i++)
66 {
67 scanf("%d",&x);
68 add1(i, x);
69 add2(i, x);
70 minx[i] = query1(i);
71 maxx[i] = query2(i);
72 }
73 for(int i=k; i<=n; i++)
74 {
75 if(i!=k) printf(" ");
76 printf("%d",minx[i]);
77 }
78 printf("\n");
79 for(int i=k; i<=n; i++)
80 {
81 if(i!=k) printf(" ");
82 printf("%d",maxx[i]);
83 }
84 printf("\n");
85
86 }
87 return 0;
88 }
