Sample Output đúng của bài được đính chính ở dưới.

Alice có một dãy số nguyên ~a_1, a_2, \dots, a_n~ là một hoán vị của dãy ~1, 2, \dots, n~. Dãy ~a_1, a_2, \dots, a_n~ được gọi là dãy hình nón tại vị trí ~k~ ~(1 \le k \le n)~ nếu dãy tăng dần từ đầu đến vị trí thứ ~k~ và giảm dần từ vị trí ~k~ đến ~n~, cụ thể: ~a_1 < a_2 < \dots < a_{k-1} < a_k > a_{k+1} > \dots > a_n~.

Alice nhận thấy, với một vị trí ~k~ ~(1 \le k \le n)~ bất kì luôn có thể thực hiện một dãy thao tác đổi chỗ hai phần tử cạnh nhau để nhận được dãy hình nón tại vị trí ~k~, nhưng để thực hiện với ít thao tác nhất thì không dễ dàng.

Yêu cầu: Với mỗi vị trí ~k~ ~(1 \le k \le n)~, hãy giúp Alice thực hiện ít thao tác đổi chỗ hai phần tử cạnh nhau nhất để từ dãy ban đầu nhận được dãy hình nón tại vị trí ~k~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 5 \cdot 10^5)~ là độ dài của dãy hoán vị;

• Dòng thứ hai chứa ~n~ số ~a_i~ ~(1 \le a_i \le n)~ mô tả dãy hoán vị được cho.

Output

• Ghi ra trên một dòng gồm ~n~ số nguyên, số thứ ~k~ là số thao tác đổi chỗ ít nhất cần sử dụng để nhận được dãy hình nón tại vị trí ~k~.

Scoring

Sample Input 1

7
1 6 7 2 5 4 3

Sample Output 1

10 4 3 2 4 7 11