#include <bits/stdc++.h>
using namespace std;
struct btNode {
int value;
bool left;
bool right;
};
struct linkedListNode {
int8_t val;
linkedListNode *next = nullptr;
bool inserted = false;
};
linkedListNode preallocLinked[1000001];
int lastNodeLnkd = 0;
static linkedListNode* get_new_lnkd_node() {
return &preallocLinked[lastNodeLnkd++];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, K;
cin >> N >> K;
vector<int> values(N);
for (auto &i: values) cin >> i;
values.push_back(30);
linkedListNode *head = get_new_lnkd_node();
linkedListNode *tail = head;
stack<btNode> stck;
stck.push(btNode{30, 0, 0});
for (int i = 0; i < N; i++) {
tail->next = get_new_lnkd_node();
tail = tail->next;
tail->val = values[i];
tail->inserted = false;
while (values[i] < stck.top().value) {
btNode &top = stck.top();
if (top.left) {
// I have to go right (left completely explored)
btNode right;
right.value = top.value - 1;
top.right = true;
stck.push(right);
} else {
// I can go left
btNode left;
left.value = top.value - 1;
top.left = true;
stck.push(left);
}
}
stck.pop(); // node is == values[i], algorithm would never run next while loop
if (i != N - 1) {
while (stck.size() > 1 && (values[i + 1] >= stck.top().value || (stck.top().right && stck.top().left))) {
btNode &top = stck.top();
if (!top.right) {
tail->next = get_new_lnkd_node();
tail = tail->next;
tail->val = top.value - 1;
tail->inserted = true;
}
stck.pop();
}
} else {
while (!stck.empty() && (values[i + 1] >= stck.top().value || (stck.top().right && stck.top().left))) {
btNode &top = stck.top();
if (!top.right) {
tail->next = get_new_lnkd_node();
tail = tail->next;
tail->val = top.value - 1;
tail->inserted = true;
}
stck.pop();
}
}
}
head = head->next;
while (head != nullptr) {
cout << (int)head->val << ' ';
head = head->next;
}
cout << '\n';
}
