题目背景
Alice 和 Bob 玩游戏。
题目描述
Alice 给出一个 1~n 的排列表示一个函数 y=f(x),即给出的第 i 个数字即为 f(i)。
现在 Bob 需要给出一个字典序尽可能小的函数 y=g(x),使得对于任意 i,f(g(i))=g(f(i))。
输入格式
第一行一个整数 n。
第二行 n 个整数,依次表示 f(1),f(2)⋯f(n)。
输出格式
共一行,n 个整数,依次表示 g(1),g(2)⋯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))=1。
- g(f(2))=f(g(2))=1。
- g(f(3))=f(g(3))=1。
- g(f(4))=f(g(4))=1。
- g(f(5))=f(g(5))=1。
样例 2 说明
- g(f(1))=f(g(1))=2。
- g(f(2))=f(g(2))=3。
- g(f(3))=f(g(3))=4。
- g(f(4))=f(g(4))=5。
- g(f(5))=f(g(5))=1。
【数据规模与约定】
对于 30% 的数据,n≤5。
对于 60% 的数据,n≤103。
对于 100% 的数据,1≤n≤8×105。