#include const int Mod = 998244353; typedef struct { int left, right, min, lc; } lazy_seg_node; void init_node(lazy_seg_node v[], int k, int l, int r) { v[k].left = l; v[k].right = r; v[k].min = 0; v[k].lc = 0; if (l < r) { init_node(v, k << 1, l, (l + r) / 2); init_node(v, (k << 1) ^ 1, (l + r) / 2 + 1, r); } } void update_segment(lazy_seg_node v[], int k, int l, int r, int c) { int i, j; if (v[k].left > r || v[k].right < l) return; else if (v[k].left >= l && v[k].right <= r) { v[k].lc += c; v[k].min += c; for (j = k, i = j >> 1; i > 0; j = i, i >>= 1) v[i].min = (v[j].min < v[j^1].min)? v[j].min: v[j^1].min; } else { if (v[k].lc != 0) { j = k << 1; v[j].min += v[k].lc; v[j^1].min += v[k].lc; v[j].lc += v[k].lc; v[j^1].lc += v[k].lc; v[k].lc = 0; } update_segment(v, k << 1, l, r, c); update_segment(v, (k << 1) ^ 1, l, r, c); } } int get_min(lazy_seg_node v[], int k, int l, int r) { int tmp[2]; if (k == 1) update_segment(v, 1, l, r, 0); if (v[k].left > r || v[k].right < l) return 100; else if (v[k].left >= l && v[k].right <= r) return v[k].min; else { tmp[0] = get_min(v, k << 1, l, r); tmp[1] = get_min(v, (k << 1) ^ 1, l, r); return (tmp[0] < tmp[1])? tmp[0]: tmp[1]; } } int BS_right(lazy_seg_node v[], int k, int l, int r) { int j, tmp; if (v[k].lc != 0) { j = k << 1; v[j].min += v[k].lc; v[j^1].min += v[k].lc; v[j].lc += v[k].lc; v[j^1].lc += v[k].lc; v[k].lc = 0; } if (v[k].min > 0 || v[k].right < l || v[k].left > r) return l - 1; else if (v[k].left == v[k].right) return v[k].left; else { tmp = BS_right(v, (k << 1) ^ 1, l, r); if (tmp >= l) return tmp; else return BS_right(v, k << 1, l, r); } } typedef struct { int x, y; } s_data; typedef struct { s_data d[200001]; int size; } stack; void push(stack* s, s_data z) { s->d[++(s->size)] = z; } s_data pop(stack* s) { return s->d[(s->size)--]; } typedef struct { int key, id; } data; void merge_sort(int n, data x[]) { static data y[200001] = {}; if (n <= 1) return; merge_sort(n / 2, &(x[0])); merge_sort((n + 1) / 2, &(x[n/2])); int i, p, q; for (i = 0, p = 0, q = n / 2; i < n; i++) { if (p >= n / 2) y[i] = x[q++]; else if (q >= n) y[i] = x[p++]; else y[i] = (x[p].key < x[q].key)? x[p++]: x[q++]; } for (i = 0; i < n; i++) x[i] = y[i]; } int main() { int i, N, K, P[200001]; scanf("%d %d", &N, &K); for (i = 1; i <= N; i++) scanf("%d", &(P[i])); s_data d; stack s_seg, s_min, s_max; s_seg.size = 0; s_min.size = 0; s_max.size = 0; d.x = 1; // node name d.y = 1; // left boundary push(&s_seg, d); d.x = P[1]; // value d.y = 1; // left boundary push(&s_min, d); push(&s_max, d); int j, k, u, n = N, par[400001], type[400001] = {}, left[400001]; lazy_seg_node v[524288]; init_node(v, 1, 1, N); for (u = 1; u <= N; u++) left[u] = u; for (i = 2; i <= N; i++) { j = i; while (s_min.size > 0) { d = pop(&s_min); if (d.x < P[i]) { push(&s_min, d); break; } update_segment(v, 1, d.y, j - 1, d.x - P[i]); j = d.y; } d.x = P[i]; d.y = j; push(&s_min, d); j = i; while (s_max.size > 0) { d = pop(&s_max); if (d.x > P[i]) { push(&s_max, d); break; } update_segment(v, 1, d.y, j - 1, P[i] - d.x); j = d.y; } d.x = P[i]; d.y = j; push(&s_max, d); update_segment(v, 1, 1, i - 1, -1); // for (j = 1; j < i; j++) printf("%d ", get_min(v, 1, j, j)); // printf("\n"); u = i; k = i; while (k > 1 && s_seg.size > 0) { j = BS_right(v, 1, 1, k - 1); if (j == 0) break; d = pop(&s_seg); if (j > d.y) { par[u] = d.x; u = par[u]; k = d.y; continue; } par[u] = ++n; par[d.x] = n; left[n] = j; u = n; k = j; if (j == d.y) continue; type[n] = 1; while (d.y != j) { d = pop(&s_seg); par[d.x] = n; } } d.x = u; d.y = k; push(&s_seg, d); } int l[400001] = {}, w, r, deg[2][400001] = {}, q[400001], head, tail = 0, cur, prev; long long dp[400001][11] = {}, tmp[2][2][11]; data *child[400001]; for (u = 1; u <= n; u++) { if (par[u] != 0) deg[0][par[u]]++; else r = u; } for (u = 1; u <= n; u++) { if (deg[0][u] == 0) q[tail++] = u; else { child[u] = (data*)malloc(sizeof(data) * (deg[0][u] + 1)); deg[1][u] = deg[0][u]; } } for (u = 1; u <= n; u++) { if (u != r) { child[par[u]][l[par[u]]].key = left[u]; child[par[u]][l[par[u]]++].id = u; } } for (head = 0; head < tail; head++) { u = q[head]; if (deg[0][u] == 0) dp[u][1] = 1; else if (type[u] == 0) { merge_sort(deg[0][u], child[u]); for (j = 1, tmp[0][0][0] = 1, tmp[0][1][0] = 0; j <= K; j++) { tmp[0][0][j] = 0; tmp[0][1][j] = 0; } for (i = 0, cur = 1, prev = 0; i < deg[0][u]; i++, cur ^= 1, prev ^= 1) { w = child[u][i].id; for (j = 0; j <= K; j++) { tmp[cur][0][j] = 0; tmp[cur][1][j] = 0; } for (j = 0; j <= K; j++) { for (k = 1; j + k <= K; k++) tmp[cur][0][j+k] += tmp[prev][0][j] * dp[w][k] % Mod; tmp[cur][1][j] += tmp[prev][0][j] + tmp[prev][1][j]; if (j < K) tmp[cur][0][j+1] += tmp[prev][1][j]; } for (j = 0; j <= K; j++) { tmp[cur][0][j] %= Mod; tmp[cur][1][j] %= Mod; } } for (j = 1; j <= K; j++) dp[u][j] = tmp[prev][0][j]; } else { for (i = 0, dp[u][0] = 1; i < deg[0][u]; i++) { w = child[u][i].id; for (j = K; j >= 0; j--) { for (k = j, dp[u][j] = 0; k > 0; k--) dp[u][j] += dp[u][j-k] * dp[w][k] % Mod; dp[u][j] %= Mod; } } } if (u == r) continue; deg[1][par[u]]--; if (deg[1][par[u]] == 0) q[tail++] = par[u]; } for (i = 1; i <= K; i++) printf("%lld\n", dp[r][i]); fflush(stdout); return 0; }