#P1963. [NOI2009] 变换序列

[NOI2009] 变换序列

题目描述

对于NN个整数0,1,,N10, 1, \cdots, N-1,一个变换序列TT可以将ii变成TiT_i,其中 Ti{0,1,,N1}T_i \in \{ 0,1,\cdots, N-1\}i=0N1{Ti}={0,1,,N1}\bigcup_{i=0}^{N-1} \{T_i\} = \{0,1,\cdots , N-1\}。 ,x,y{0,1,,N1}\forall x,y \in \{0,1,\cdots , N-1\},定义x和y之间的距离D(x,y)=min{xy,Nxy}D(x,y)=min\{|x-y|,N-|x-y|\} 。给定每个iiTiT_i之间的距离D(i,Ti)D(i,T_i),你需要求出一个满足要求的变换序列T。如果有多个满足条件的序列,输出其中字典序最小的一个。

说明:对于两个变换序列SSTT,如果存在p<Np<N,满足对于i=0,1,p1i=0,1,\cdots p-1Si=TiS_i=T_iSp<TpS_p<T_p,我们称SSTT字典序小。

输入格式

第一行包含一个整数NN,表示序列的长度。接下来的一行包含NN个整数DiD_i,其中DiD_i表示iiTiT_i之间的距离。

输出格式

如果至少存在一个满足要求的变换序列TT,则输出文件中包含一行NN个整数,表示你计算得到的字典序最小的TT;否则输出No Answer(不含引号)。注意:输出文件中相邻两个数之间用一个空格分开,行末不包含多余空格。

5
1 1 2 2 1
1 2 4 0 3

提示

对于30%的数据,满足:N<=50;

对于60%的数据,满足:N<=500;

对于100%的数据,满足:N<=10000。