어느 러닝 클럽이 회원을 모집하며 빠르게 성장하고 있으며, 매일 정확히 한 명의 신입 회원이 가입합니다. 모든 회원은 특정한 초기 실력 수준을 가지고 들어오며, 도착한 순서에 따라 고유한 ID를 부여받습니다.

매일이 끝날 때마다 코치는 클럽의 "총 잠재력"이라고 부르는 지표를 계산하는 것을 좋아합니다. 이 값은 단순히 현재 모든 회원의 개인 잠재력의 합입니다. 회원들의 동기를 부여하기 위해, 회원의 잠재력은 단 한 번의 고강도 훈련을 포함하는 가상의 "만약에" 시나리오를 통해 계산됩니다.

이 가상의 훈련에서 회원은 자신의 실력 수준을 일시적으로 높이기 위해 일정량의 노력을 기울이기로 선택할 수 있습니다. 노력을 $1$단위 소모할 때마다 실력 수준은 정확히 $1$단위 증가합니다. 그 대가로, 현재 클럽에 있는 다른 회원 중 다음 조건을 만족하는 회원마다 $1$단위의 "행복도"를 얻습니다:

• 자신보다 엄격하게 나중에 클럽에 가입했으며,
• 원래는 자신보다 엄격하게 실력이 더 높았으나, 이번 훈련 덕분에 따라잡혔거나 추월당함.

이 계산 중에는 해당 회원의 실력만 증가하며, 다른 모든 회원의 실력 수준은 원래 값으로 고정되어 있음에 유의하세요.

단일 회원의 잠재력은 노력 수준을 최적으로 선택하여 달성할 수 있는 순수익(행복도에서 노력을 뺀 값)의 가능한 최댓값으로 정의됩니다. 이러한 훈련은 전적으로 이론적인 것이며 코치의 일일 보고서에만 사용되고, 회원들의 실제 실력 수준은 날이 갈수록 변하지 않습니다.

여러분의 작업은 모집 기간의 매일이 끝날 때마다 코치가 클럽의 총 잠재력을 계산하는 것을 돕는 것입니다.

입력

입력의 첫 번째 줄에는 클럽이 회원을 모집하는 일수를 나타내는 정수 $n$ ($1 \le n \le 10^5$)이 주어집니다.

두 번째 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)이 주어지며, 여기서 $a_i$는 $i$번째 날에 가입하는 회원의 초기 실력 수준입니다.

출력

한 줄에 $n$개의 정수를 출력합니다. $k$번째 정수는 $k$번째 날이 끝날 때 클럽의 총 잠재력이어야 합니다.

예제

입력 1

8
1 2 3 1 2 3 2 3

출력 1

0 0 0 0 1 3 5 9

입력 2

1
1

출력 2

0

노트

예제 1 설명: $5$번째 날에는 실력 수준이 $[1, 2, 3, 1, 2]$인 $5$명의 회원이 있습니다. 회원 $1$의 경우: 더 늦게 가입하고 실력이 엄격하게 더 높은 회원이 $3$명 있습니다: 회원 $2$, 회원 $3$, 회원 $5$. 회원 $1$의 최대 잠재력은 $1$이며, 다음 전략 중 하나로 달성됩니다:

• 회원 $1$이 $1$단위의 노력을 기울이면 실력은 $2$가 됩니다. 회원 $2$와 회원 $5$를 따라잡거나 추월하게 됩니다. 행복도는 $2$단위이고, 순수익은 $2 - 1 = 1$단위입니다.
• 회원 $1$이 $2$단위의 노력을 기울이면 실력은 $3$이 됩니다. 회원 $2$, $3$, $5$를 따라잡거나 추월하게 됩니다. 행복도는 $3$단위이고, 순수익은 $3 - 2 = 1$단위입니다.

다른 회원들의 최대 잠재력은 $0$입니다. 따라서 $5$번째 날의 총 잠재력은 $1$입니다.

$8$번째 날에는 실력 수준이 $[1, 2, 3, 1, 2, 3, 2, 3]$인 $8$명의 회원이 있습니다. 최적의 노력은 $[2, 1, 0, 2, 1, 0, 1, 0]$이고 이에 대응하는 최대 잠재력은 $[4, 2, 0, 2, 1, 0, 0, 0]$입니다.