### PROBLEM LINK:

**Author:** Arjun Arul

**Tester:** Hasan Jaddouh

**Editorialist:** Hussain Kara Fallah

### PROBLEM EXPLANATION

Given an array consisting of **N** integers. Let’s construct a directed acyclic graph of **N+1** nodes. If there is a subsequence **S _{1}** ending at position

**U**which cannot be formed with all elements to the left of

**A**, let’s denote by

_{U}**S**the subsequence resulting from appending

_{2}**A**to

_{V}**S**

_{1}**(U < V)**

An edge is added from node **U** to node **V** if and only if the subsequence **S _{2}** cannot be formed with all elements to the left of

**A**. You are given a DAG with

_{V}**N+1**nodes and

**M**edges, you are asked to restore the lexicographically minimum array which this graph corresponds to or state that data is inconsistent.

Please note that node 0 represents the empty subsequence.

**(1 ≤ N,M ≤ 10 ^{5})**

### DIFFICULTY:

easy-medium

### PREREQUISITES:

Sortings

### EXPLANATION:

### Observation 1:

Let’s denote by L_i the adjacency list of the i-th node.

Note that the out degree of node 0 (size of L_0) is equal to the number of distinct elements in our array (let’s denote it by K). Because each position that presents in this list refers to the first occurrence of a **(new)** number since an edge from node 0 to other node corresponds to a subsequence of size 1.

### Observation 2:

Consider an arbitrary position P, you can note that the subsequence containing all elements A_i (1 \leq i \leq P) cannot be formed without considering all elements till A_P let’s denote this subsequence by S_1. If there is an edge (P \rightarrow Q), it means that Q must be the first occurrence (to the right of P) of one of our numbers (Why?), because if there was an earlier occurrence R (R < Q), then the subsequence S_1 + A_Q (+ denotes concatenation) could be formed with the first R elements, and that means an edge (P \rightarrow R) must exist and the other edge (P \rightarrow Q) mustn’t **(contradiction)**.

### Observation 3:

Let’s consider the list L_{P} and the list L_{P - 1}. The size of L_{P} must be equal or less by one than the size of L_{P - 1}. Let’s think about earliest occurrences of our K numbers when looking to the right of A_{P-1}, you can see that all of them will remain the same (when looking to the right of A_P), **EXCEPT** for 1 element which is A_P. P is present in L_{P - 1} (clearly it’s the earliest occurrence of A_P), but in L_{P} it will be replaced by the first occurrence to the right of P (so lists sizes will stay the same), or there may be no next occurrence (if P was the last occurrence of A_P) then size of L_{P} would be less by 1.

Let’s assign numbers from 1 to K to all positions present in **L _{0}** (in increasing order of position). After that let’s consider each 2 consecutive lists L_{P}, L_{P - 1}. All elements of L_{P - 1} must be present in L_{P} except for one element for sure which is equal to P. All elements of L_{P} must be present in L_{P - 1} except one number X which is equal to A_P, so we should assign A_X = A_P (if size of L_{P} is less by one than the size of L_{P-1} then we don’t need to look for it.

### Corner Case

While processing elements from left to right, if we come to an element which hasn’t been processed then our data is inconsistent. Any position P must exist in L_{P-1} and reaching an unassigned number means that it’s not existed in L_{P-1} otherwise we would have assigned it to a value.

Solution runs in O(M log M)

### AUTHOR’S AND TESTER’S SOLUTIONS:

**AUTHOR’s solution**: Can be found here

**TESTER’s solution**: Can be found here

**EDITORIALIST’s solution**: Can be found here