Problem Description

Walk Alone is a master of strings, but he has become bored with traditional string algorithms such as the KMP algorithm, so recently he has been thinking about a reversed version of KMP. Here is the problem he proposed:

You are given an integer sequence $a$ of length $n$. For any integer $i\ (1\le i\le n)$, it satisfies $0\le a_i<i$. You need to construct another integer sequence $s$ that satisfies the following conditions:

• The sequence $s$ has length $n$, and every element $s_i$ satisfies $1\le s_i\le n$.
• For all integers $i\ (1\le i\le n)$ and $j\ (1\le j\le a_i)$, it holds that $s_{j}=s_{i-a_i+j}$.
• Under the above conditions, the number of distinct elements appearing in sequence $s$ is as large as possible.

Of course, Walk Alone can solve this problem easily, but he wants to use it as a test for you.

Input Format

The first line contains an integer $n\ (1\le n\le 2\cdot 10^5)$, which denotes the length of sequence $a$.

The second line contains $n$ integers, where the $i$-th integer is defined as $a_i\ (0\le a_i<i)$.

Output Format

Output $n$ integers separated by spaces, where the $i$-th integer is defined as $s_i$. If there are multiple valid answers, output the lexicographically smallest one.

5
0 0 1 2 3

1 2 1 2 1 

11
0 0 0 0 2 1 0 0 3 0 1

1 2 3 1 2 1 1 2 3 4 1 

Hint

Translated by ChatGPT 5