#P2582. 函数

函数

题目背景

Alice 和 Bob 玩游戏。

题目描述

Alice 给出一个 11~nn 的排列表示一个函数 y=f(x)y=f(x),即给出的第 ii 个数字即为 f(i)f(i)

现在 Bob 需要给出一个字典序尽可能小的函数 y=g(x)y=g(x),使得对于任意 iif(g(i))=g(f(i))f(g(i))=g(f(i))

输入格式

第一行一个整数 nn

第二行 nn 个整数,依次表示 f(1),f(2)f(n)f(1),f(2) \cdots f(n)

输出格式

共一行,nn 个整数,依次表示 g(1),g(2)g(n)g(1),g(2) \cdots g(n)

5
1 2 3 4 5
1 1 1 1 1
5
2 3 4 5 1
1 2 3 4 5

提示

【样例解释】

样例 1 说明

  • g(f(1))=f(g(1))=1g(f(1))=f(g(1))=1
  • g(f(2))=f(g(2))=1g(f(2))=f(g(2))=1
  • g(f(3))=f(g(3))=1g(f(3))=f(g(3))=1
  • g(f(4))=f(g(4))=1g(f(4))=f(g(4))=1
  • g(f(5))=f(g(5))=1g(f(5))=f(g(5))=1

样例 2 说明

  • g(f(1))=f(g(1))=2g(f(1))=f(g(1))=2
  • g(f(2))=f(g(2))=3g(f(2))=f(g(2))=3
  • g(f(3))=f(g(3))=4g(f(3))=f(g(3))=4
  • g(f(4))=f(g(4))=5g(f(4))=f(g(4))=5
  • g(f(5))=f(g(5))=1g(f(5))=f(g(5))=1

【数据规模与约定】

对于 30%30\% 的数据,n5n \le 5。 对于 60%60\% 的数据,n103n \le 10^3。 对于 100%100\% 的数据,1n8×1051 \le n \le 8 \times 10^5