## Algorithm

D. Array Restoration
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Initially there was an array a consisting of n integers. Positions in it are numbered from 11 to n.

Exactly q queries were performed on the array. During the i-th query some segment (li,ri)(��,��) (1lirin)(1≤��≤��≤�) was selected and values of elements on positions from li�� to ri�� inclusive got changed to i. The order of the queries couldn't be changed and all q queries were applied. It is also known that every position from 11 to n got covered by at least one segment.

We could have offered you the problem about checking if some given array (consisting of n integers with values from 11 to q) can be obtained by the aforementioned queries. However, we decided that it will come too easy for you.

So the enhancement we introduced to it is the following. Some set of positions (possibly empty) in this array is selected and values of elements on these positions are set to 00.

Your task is to check if this array can be obtained by the aforementioned queries. Also if it can be obtained then restore this array.

If there are multiple possible arrays then print any of them.

Input

The first line contains two integers n and q (1n,q21051≤�,�≤2⋅105) — the number of elements of the array and the number of queries perfomed on it.

The second line contains n integer numbers a1,a2,,an�1,�2,…,�� (0aiq0≤��≤�) — the resulting array. If element at some position j is equal to 00 then the value of element at this position can be any integer from 11 to q.

Output

Print "YES" if the array a can be obtained by performing q queries. Segments (li,ri)(��,��) (1lirin)(1≤��≤��≤�) are chosen separately for each query. Every position from 11 to n should be covered by at least one segment.

Otherwise print "NO".

If some array can be obtained then print n integers on the second line — the i-th number should be equal to the i-th element of the resulting array and should have value from 11 to q. This array should be obtainable by performing exactly q queries.

If there are multiple possible arrays then print any of them.

Examples
input
Copy
4 31 0 2 3
output
Copy
YES1 2 2 3
input
Copy
3 1010 10 10
output
Copy
YES10 10 10
input
Copy
5 66 5 6 2 2
output
Copy
NO
input
Copy
3 50 0 0
output
Copy
YES5 4 2
Note

In the first example you can also replace 00 with 11 but not with 33.

In the second example it doesn't really matter what segments to choose until query 1010 when the segment is (1,3)(1,3).

The third example showcases the fact that the order of queries can't be changed, you can't firstly set (1,3)(1,3) to 66 and after that change (2,2)(2,2) to 55. The segment of 55 should be applied before segment of 66.

There is a lot of correct resulting arrays for the fourth example.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

int const N = 2e5 + 10;
int n, q, a[N], b[N], seg[4 * N], lazy[4 * N];
pair<int, int> ss[N];

void pro(int at, int l, int r) {
seg[at] = lazy[at];
if(l != r) {
lazy[at << 1] = lazy[at];
lazy[at << 1 | 1] = lazy[at];
}
lazy[at] = 0;
}

int s, e, v;
void update(int at, int l, int r) {
if(lazy[at] != 0)
pro(at, l, r);

if(s > r || e < l)
return;

if(l >= s && r <= e) {
lazy[at] = v;
pro(at, l, r);
return;
}

int mid = (l + r) >> 1;
update(at << 1, l, mid);
update(at << 1 | 1, mid + 1, r);
}

int get(int at, int l, int r) {
if(lazy[at] != 0)
pro(at, l, r);

if(l >= s && r <= e)
return seg[at];

int mid = (l + r) >> 1;
if(s >= l && s <= mid)
return get(at << 1, l, mid);
else
return get(at << 1 | 1, mid + 1, r);
}

int get(int i, int d) {
if(d == 1) {
for(int j = i; j <= n; ++j)
if(b[j] != 0)
return b[j];
return -1;
} else {
for(int j = i; j >= 1; --j)
if(b[j] != 0)
return b[j];
return q;
}
}

int main() {
scanf("%d %d", &n, &q);
for(int i = 1; i <= n; ++i) {
scanf("%d", a + i);
if(ss[a[i]].F == 0)
ss[a[i]].F = i;
ss[a[i]].S = i;
}

for(int i = 1; i <= q; ++i) {
if(ss[i].F == 0)
continue;
s = ss[i].F, e = ss[i].S, v = i;
update(1, 1, n);
}

for(int i = 1; i <= n; ++i) {
s = i, e = i;
b[i] = get(1, 1, n);
}

for(int i = 1; i <= n; ++i)
if(a[i] != b[i] && a[i] != 0) {
puts("NO");
return 0;
}

for(int i = 1; i <= n; ++i)
if(b[i] == 0) {
int cur = get(i + 1, 1);
if(cur == -1)
cur = get(i - 1, 2);
while(b[i] == 0)
b[i++] = cur;
--i;
}

bool ok = false;
for(int i = 1; i <= n; ++i)
if(b[i] == q) {
ok = true;
break;
}

if(!ok) {
for(int i = 1; i <= n; ++i)
if(a[i] == 0) {
b[i] = q;
ok = true;
break;
}
}

if(!ok) {
puts("NO");
return 0;
}

puts("YES");
for(int i = 1; i <= n; ++i)
printf("%s%d", i == 1 ? "" : " ", b[i]);
puts("");

return 0;
}
Copy The Code &

Input

cmd
4 3
1 0 2 3

Output

cmd
YES
1 2 2 3