Limits 1s, 512 MB

Consider an array of 'N' integers which is indexed from '1' to 'N'.
Exactly 'Q' queries numbered from '1' to 'Q' are applied on them in increasing order.
For the 'i'-th query, an arbitrary range [L, R] of the array is selected (1 <= L <= R <= N) and each value from index 'L' to index 'R' gets changed to 'i'. It is guaranteed that every index of the array is covered by at least one range.

You are given an array of 'N' integers where value of the array is from '0' to 'Q'.
Value '0' means the value is missing which can be restored to any integer from '1' to 'Q'.
Value 'i' (1 <= i <= Q) means 'i' was stored in the array while 'i'-th query was applied.
Your task is to check if the given array can be acquired after applying the 'Q' queries.

If it is possible to acquire the given array, restore the missing values of the array.
Array restoration may be possible with multiple solution. If multiple solutions are available, you have to restore the missing values such that the array is lexicographically minimum.


The first line of input file contains an integer 'T' (1 <= T <= 60) denoting the test case of input.
Each test case consists of two lines.
First line contains two integers 'N' and 'Q' (1 <= N, Q <= 100000),
where 'N' is the size of the array and 'Q' is the number of queries.
Second line of each test case contains 'N' integers 'A1', 'A2', ... 'An' (0 <= Ai <= Q).


Print 'YES' with the case number if array can be restored.
And then in the second line print the 'N' integers of the array.
Print 'NO' with the case number if array can't be restored.


5 3
2 0 1 3 3
3 4
0 0 0
4 5
5 5 5 5
4 3
2 1 0 2
Case 1: YES
2 1 1 3 3
Case 2: YES
1 1 4
Case 3: YES
5 5 5 5
Case 4: NO


Login to submit.


62% Solution Ratio
ju_trojanEarliest, Jan '20
Kuddus.6068Fastest, 0.1s
MursaleenLightest, 2.9 MB
MursaleenShortest, 1214B
Toph uses cookies. By continuing you agree to our Cookie Policy.