AcWing 1242.修改数组（蓝桥杯真题）

"""
并查集：
从前往后，将每个a[i]的祖宗节点置为比a[i]大1的数
如果a[i]之前没出现过，那么其祖宗节点是自己，可以直接输出
否则如果a[i]之前出现过，那么其祖宗节点是比它大1的数，那么第二次出现a[i]的时候会输出其祖宗节点

数据范围分析：如果a全部是1000000，N为100000，那么最大的祖宗节点是1100000，因此初始化p的时候要注意
"""
import sys

sys.setrecursionlimit(1000000)
input = sys.stdin.readline
print = sys.stdout.write

def find(x):
    if x != p[x]:
        p[x] = find(p[x])
    return p[x]

n = int(input())
a = [0] + list(map(int, input().strip().split()))

p = [i for i in range(1100010)]
for i in range(1, n + 1):
    x = find(a[i])  # 先看自己的祖宗节点，输出
    print(str(x) + ' ')
    p[x] = x + 1  # 原来的祖宗节点用过了，要找题意需要将小的值接在大的值后面