405906: GYM102155 H Sketch

Given a sequence a consisting of integers a₁, ..., a_n, consider all its non-decreasing subsequences of length k. Among all of these take the one with smallest last element. We denote the value of this element with s_k.

The sequence s(a) = s₁, ..., s_l is a sketch for sequence a, where l is the length of the longest non-decreasing subsequence of a.

Building a sketch of the sequence is a standard task while finding the length of the longest non-decreasing subsequence. Here we consider an opposite problem: given a sketch with some missing entries, find any sequence producing this sketch.

Formally, you are given a sequence t₁, ..., t_k where each element is either a positive integer or  - 1. You have to find a sequence a₁, ..., a_n with each element being an integer between 1 and m, inclusive, satisfying the following properties: length of the sketch of a should be equal to k, and for each index i between 1 and k, if t_i ≠  - 1, then s_i = t_i should hold.

First line contains three integers k, n, m (1 ≤ k ≤ 300 000, 1 ≤ n ≤ 300 000, 1 ≤ m ≤ 10⁹), the length of the sketch, the length of the desired sequence and the upper bound on element values respectively.

Next line contains k numbers t₁, ..., t_k (1 ≤ t_i ≤ m or t_i =  - 1), the sketch itself.

If a sequence with such sketch exists, output the elements of a desired sequence. In case of multiple answers you may output any of them.

If no valid sequence exists, output a single integer  - 1.

3 4 10
3 7 7

3 7 8 7

3 5 10
3 -1 7

3 6 5 4 7

4 2 10
1 2 3 4

-1

Sketch of the answer sequence in example 2: 3 4 7.