// yukicoder: No.318 学学学学学 // 2019.7.24 bal4u #include #if 1 #define gc() getchar_unlocked() #define pc(c) putchar_unlocked(c) #else #define gc() getchar() #define pc(c) putchar(c) #endif int in() { // 非負整数の入力 int n = 0, c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } void out(int n) { // 正整数の表示 int i; char b[20]; i = 0; while (n) b[i++] = n % 10 + '0', n /= 10; while (i--) pc(b[i]); } void outs(int k, int v) { // 連続した正整数の表示 int i, ii; char b[20]; i = 0; while (v) b[i++] = v % 10 + '0', v /= 10; while (k--) { pc(' '); ii = i; while (ii--) pc(b[ii]); } } #define HASHSIZ 4999999 typedef struct { int v, id; } HASH; HASH hash[HASHSIZ+5], *hashend = hash+HASHSIZ; int insert(int v, int id) { HASH *p = hash + v % HASHSIZ; while (p->v) { if (p->v == v) return p->id; if (++p == hashend) p = hash; } p->v = v, p->id = id; return -1; } // 優先度付きキュー #define QSIZE 110000 #define PARENT(i) ((i)>>1) #define LEFT(i) ((i)<<1) #define RIGHT(i) (((i)<<1)+1) typedef struct { int v, b; } QUE; QUE que[QSIZE+5]; int qsize; void max_heapify(int i) { int l, r, max; QUE qt; l = LEFT(i), r = RIGHT(i); if (l < qsize && que[l].v > que[i].v) max = l; else max = i; if (r < qsize && que[r].v > que[max].v) max = r; if (max != i) { qt = que[i], que[i] = que[max], que[max] = qt; max_heapify(max); } } void deq() { que[0] = que[--qsize]; max_heapify(0); } void enq(int v, int b) { int i, max; QUE qt; i = qsize++; que[i].v = v, que[i].b = b; while (i > 0 && que[max = PARENT(i)].v < que[i].v) { qt = que[i]; que[i] = que[max], que[max] = qt; i = max; } } typedef struct { int v, a, b; } T; T t[100005]; int w; int main() { int i, j, v, a, b, n; n = in(); for (i = 0; i < n; i++) { if ((j = insert(v = in(), w)) < 0) t[w].v = v, t[w].a = t[w].b = i, w++; else t[j].b = i; } //for (i = 0; i < w; i++) printf("(%d,%d,%d) ", t[i].v, t[i].a, t[i].b); //printf("\n"); i = 0, v = t[0].v, a = 0, b = t[0].b; out(v); if (b > 0 && v > t[1].v) a++; else { if (t[++i].b < b) enq(v, b); v = t[i].v, a = t[i].a, b = t[i].b; } while (++i < w) { if (t[i].a <= b) { if (v < t[i].v) { // もっと強いやつが重ねてきた outs(t[i].a-a, v); if (t[i].b < b) enq(v, b); v = t[i].v, a = t[i].a, b = t[i].b; } else { // 弱いやつが重ねてきた if (b < t[i].b) enq(t[i].v, t[i].b); } } else { // (v,a,b)が終了する運命 outs(b-a+1, v), a = b+1; // queかt[i]から候補を選ぶ while (qsize) { v = que[0].v, b = que[0].b, deq(); if (a <= b) { if (t[i].a <= b) { i--; break; } else outs(b-a+1, v), a = b+1; } } if (b < a) v = t[i].v, a = t[i].a, b = t[i].b; } } outs(b-a+1, v), a = b+1; while (qsize) { if (a <= que[0].b) outs(que[0].b-a+1, que[0].v), a = que[0].b+1; deq(); } pc('\n'); return 0; }