Operation of Frequency of Appearance

Time Limit : 1 sec, Memory Limit : 65536 KB

Operation of Frequency of Appearance

有限数列の変換操作に出現頻度操作というものがあります。数列 S ={ s1 , s 2 ,... s n } の変換結果は同じ長さの 数列となります。その結果を C= { c1 , c 2 , ..., c n } とすると、 c i は数列 S における s i の個数を表します。

例えば S ={3,4,1,5,9,2,6,5,3}ならば C ={2,1,1,2,1,1,1,2,2}となります。さらにこの数列 C に出現頻度操作を行う と P ={4,5,5,4,5,5,5,4,4}を得ます。この数列は出現頻度操作で変わることがありません。 このような数列 P を数列 S の不動点と呼びます。どのような数列に対しても出現頻度操作を繰り返せば、その不 動点を求めることが出来るということが知られています。

下の例は出現頻度操作の手順を示したものです。1 行目を数列 S 、2 行目を数列 C 、最終行を数列 P としま す。数列 S の最初の要素( s1 =2)と同じ数は 3 個あるので数列 C の最初の要素 c1 は 3、次の要素( s 2 =7)と同じ数 は 2 個あるので c 2 =2、といった具合に個数を数え c i を求めていきます。

数列の長さ n と数列 S を入力し、不動点の数列 P および、P を得るために実行した出現頻度操作の最小の回 数を出力して終了するプログラムを作成してください。 ただし、n は 12 以下とします。

Input

複数のデータセットが与えられます。各データセットは以下のとおり:

1 行目は数列の長さ n(整数)
2 行目は数列 S の要素 s1 , s 2 ......... s n (n 個の整数;半角空白区切り)

入力は0一つの行で終わります。

Output

各データセットについて以下を出力してください:

出現頻度操作の最小の実行回数(整数)
対応する不動点の数列 P の要素 p1 p 2 ...... p n (n 個の整数;半角空白区切り)

Sample Input

10
4 5 1 1 4 5 12 3 5 4
0

Output for the Sample Input

3
6 6 4 4 6 6 4 4 6 6

Source: PC Koshien 2005 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2005
http://www.pref.fukushima.jp/pc-concours/