Toàn bộ \(N\) thành viên của Ủy ban Olympic Tin học Nhật Bản, trong đó có chủ tịch K, cùng đến một nhà hàng Trung Hoa.

Bàn ăn là một chiếc bàn tròn với \(N\) chỗ ngồi cách đều nhau. Ở giữa bàn có một mâm xoay để đặt các món ăn. Các thành viên ngồi vào \(N\) chỗ; chủ tịch K được đánh số \(1\), các thành viên tiếp theo được đánh số \(2,3,\ldots,N\) theo chiều ngược kim đồng hồ.

Ủy ban gọi \(N\) món ăn khác nhau, mỗi món một phần, và đặt chúng trên mâm xoay. Ban đầu, món \(i\) nằm ngay trước mặt thành viên \(i\) với mọi \(1 \le i \le N\). Mỗi thành viên ngoài chủ tịch K đã chọn sẵn một món muốn ăn: thành viên \(i\) muốn ăn món \(A_i\), với \(2 \le i \le N\).

Mâm xoay có thể quay theo cả hai chiều, mỗi đơn vị quay là một góc:

Ví dụ, nếu quay mâm ngược chiều kim đồng hồ một đơn vị từ trạng thái ban đầu, món \(N\) sẽ ở trước mặt chủ tịch K, còn món \(i-1\) sẽ ở trước mặt thành viên \(i\) với \(2 \le i \le N\). Một thành viên chỉ có thể ăn một món khi món đó nằm ngay trước mặt mình.

Vì chủ tịch K rất được kính trọng, ông là người đầu tiên quay mâm để món \(k\) (\(1 \le k \le N\)) đến trước mặt mình rồi ăn món đó. Sau khi chủ tịch ăn xong, các thành viên còn lại lần lượt quay mâm để món họ muốn ăn đến trước mặt mình rồi ăn. Thứ tự của các thành viên còn lại có thể tùy ý. Mỗi món đều có đủ thức ăn và không bao giờ hết.

Yêu cầu

Để chuẩn bị cho mọi lựa chọn của chủ tịch K, với mỗi \(k\) từ \(1\) đến \(N\), hãy tính tổng số đơn vị quay mâm nhỏ nhất để tất cả các thành viên đều được ăn món mình chọn. Tổng này bao gồm cả lần quay đầu tiên của chủ tịch K.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\), là số thành viên.
• \(N-1\) dòng tiếp theo mô tả món ăn mà các thành viên muốn ăn. Dòng thứ \(i\) của dữ liệu vào (\(2 \le i \le N\)) chứa số nguyên \(A_i\).

Dữ liệu ra

In ra đầu ra chuẩn \(N\) dòng. Dòng thứ \(k\) (\(1 \le k \le N\)) chứa tổng số đơn vị quay mâm nhỏ nhất khi chủ tịch K chọn món \(k\). Một đơn vị quay tương ứng với góc \(360/N\) độ.

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le A_i \le N\) với mọi \(2 \le i \le N\).

Phân nhóm

• Các bộ kiểm thử chiếm \(10\%\) tổng số điểm thỏa mãn \(N \le 10\).
• Các bộ kiểm thử chiếm \(40\%\) tổng số điểm thỏa mãn \(N \le 1\,000\).

Các tỉ lệ trên là các điều kiện tích lũy; không cộng chúng thành các nhóm điểm độc lập.

Ví dụ

5
3
5
3
2

4
4
5
6
4