시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 512 MB 1 1 1 100.000%

문제

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

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

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

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

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

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

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

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

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

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

입력

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

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

출력

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

제한

  • 2 ≤ N ≤ 100 000 情報オリンピック日本委員会の人数
  • 1 ≤ Ai ≤ N 委員 i が食べたい料理

예제 입력 1

5
3
5
3
2

예제 출력 1

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 を出力する.