Chinese(中華料理) - joi2012-day4

時間制限: 1.5秒

メモリ制限: 64MB

K理事長を含む情報オリンピック日本委員会の N 人全員で中華料理店にやってきた．

中華料理店のテーブルは円卓で，N 個の座席が等間隔に並んでいる．また，中央には料理が置かれる回転台が乗っている．N 人の委員は N 個の座席に座り，K 理事長を 1 として，そこから反時計回りに 2, 3, … N と委員に番号がつけられた．委員会は N種類の料理を 1 個ずつ注文し，それらの料理が回転台の上に置かれた．料理は委員の目の前に置かれており，委員 i の目の前に置かれた料理は料理 i (1 \leqq i \leqq N) である．K 理事長以外の委員にはそれぞれ食べたい料理が 1 つ決まっており，委員 i (2 \leqq i \leqq N) が食べたい料理は A_i である．

回転台は (360 / N) 度単位で時計回り・反時計回りのどちらの向きにも回転させることができる．

例えば，回転台を反時計回りに 1 単位回転させると，K 理事長の目の前には料理 N が，委員 i (2 \leqq i \leqq N) の目の前には料理 i – 1 が来る．

ある委員がある料理を食べるには，その料理がその委員の目の前に来るように回転台を回さなければならない．

情報オリンピック日本委員会では K 理事長はとても尊敬されているため，最初に K 理事長が回転台を回し，料理 k (1 \leqq k \leqq N) が目の前に来るようにしてその料理を食べる．

K 理事長が料理を食べた後，K 理事長以外の委員たちはそれぞれ自分の食べたい料理が目の前に来るように回転台を回し，その料理を食べる．ただし，K 理事長以外の委員たちが回転台を回す順番はどのような順番でも良い．

また，それぞれの料理は量が十分にあり，食べて無くなることは無いものとする．

K 理事長が何を食べても対応できるよう，全員が料理を食べられ，かつ回転台を回す量の合計が最小になるように，K 理事長以外の委員が回転台を回す順番と回し方を各 k について前もって決めておきたい．

課題

各委員 i (2 \leqq i \leqq N) が食べたい料理 A_i が与えられたとき，K 理事長が食べる料理 k (1 \leqq k \leqq N) のそれぞれについて，回転台を回す量の合計の最小値を (360 / N) 度を 1 単位として求めよ．

制限

`2 \leqq N \leqq 100\,000`	情報オリンピック日本委員会の人数
`1 \leqq A_i \leqq N`	委員 `i` が食べたい料理

入力

標準入力から以下の入力を読み込め．

1 行目には整数 N が書かれており，情報オリンピック日本委員会の人数を表す．
続く N-1 行には，各委員の食べたい料理の情報が与えられる．i (2 \leqq i \leqq N) 行目には整数 A_i が書かれている．これは委員 i の食べたい料理が A_i であることを表す．

出力

出力は N 行からなる．k 行目 (1 \leqq k \leqq N) に，K 理事長が料理 k を食べるときの，回転台を回す量の合計の最小値を表す整数を出力せよ．ただし，回転台を回す量は，(360 / N) 度を 1 単位とする．

採点基準

採点用データのうち，配点の 10% 分については N \leqq 10 を満たす．
採点用データのうち，配点の 40% 分については N \leqq 1\,000 を満たす．

入出力の例

入力例1	出力例1
`5 3 5 3 2`	`4 4 5 6 4`

この場合，円卓には 5 人の委員が図のように座っている．

例えば，k=3 の場合(K 理事長が料理 3 を食べる場合)を考えると，回転台を回す量の合計が最小になるような回し方は以下の通りである．

K 理事長(委員1)が回転台を時計回りに 2 単位回し，料理 3 を食べる．
委員 3 が回転台を回さずに料理 5 を食べる．
委員 5 が回転台を回さずに料理 2 を食べる．
委員 2 が回転台を反時計回りに 1 単位回し，料理 3 を食べる．
委員 4 が回転台を反時計回りに 2 単位回し，料理 3 を食べる．

この時，回転台を回す量の合計は 2+1+2=5 単位となるので，出力の 3 行目には 5 を出力する．