Sebuah klub lari sedang merekrut anggota dan berkembang pesat, dengan tepat satu anggota baru bergabung setiap harinya. Setiap anggota datang dengan tingkat keahlian awal tertentu, dan mereka diberi ID unik berdasarkan urutan kedatangan mereka.

Di penghujung setiap hari, Pelatih suka menghitung metrik yang ia sebut "total potensi" klub. Nilai ini hanyalah jumlah dari potensi individu semua anggota saat ini. Untuk menjaga motivasi para anggota, potensi seorang anggota dihitung melalui skenario hipotesis "bagaimana-jika" yang melibatkan satu latihan intensif.

Dalam latihan imajiner ini, seorang anggota dapat memilih untuk mengerahkan sejumlah usaha guna meningkatkan tingkat keahlian mereka secara sementara. Untuk setiap $1$ satuan usaha yang mereka keluarkan, tingkat keahlian mereka meningkat tepat $1$ satuan. Sebagai imbalannya, mereka memperoleh $1$ satuan "kebahagiaan" untuk setiap anggota lain yang saat ini berada di klub yang:

• bergabung dengan klub secara ketat setelah mereka; dan
• awalnya memiliki keahlian yang secara ketat lebih tinggi daripada mereka, tetapi sekarang telahterkejar atau terlampaui berkat latihan tersebut.

Perhatikan bahwa selama perhitungan ini, hanya tingkat keahlian anggota tersebut yang ditingkatkan, sementara tingkat keahlian semua anggota lainnya tetap pada nilai aslinya.

Potensi seorang anggota didefinisikan sebagai nilai maksimum yang mungkin dari keuntungan bersih mereka (kebahagiaan dikurangi usaha) yang dapat mereka capai dengan memilih tingkat usaha secara optimal. Latihan ini sepenuhnya bersifat teoretis; hanya digunakan untuk laporan harian Pelatih, dan tingkat keahlian aktual para anggota tetap tidak berubah dari hari ke hari.

Tugas Anda adalah membantu Pelatih menghitung total potensi klub di penghujung setiap hari selama periode perekrutan.

Masukan

Baris pertama masukan berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^5$), yang menyatakan jumlah hari klub merekrut anggota.

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), di mana $a_i$ adalah tingkat keahlian awal anggota yang bergabung pada hari ke-$i$.

Keluaran

Keluarkan $n$ bilangan bulat dalam satu baris. Bilangan bulat ke-$k$ harus berupa total potensi klub pada akhir hari ke-$k$.

Contoh

Masukan 1

8
1 2 3 1 2 3 2 3

Keluaran 1

0 0 0 0 1 3 5 9

Masukan 2

1
1

Keluaran 2

0

Catatan

Penjelasan Contoh 1: Pada hari ke-$5$, terdapat $5$ anggota dengan tingkat keahlian $[1, 2, 3, 1, 2]$. Untuk anggota $1$: Terdapat $3$ anggota yang bergabung lebih lambat dengan keahlian yang secara ketat lebih tinggi: anggota $2$, anggota $3$, dan anggota $5$. Potensi maksimum untuk anggota $1$ adalah $1$, yang dicapai melalui salah satu strategi berikut:

• Jika anggota $1$ mengeluarkan $1$ satuan usaha, keahliannya menjadi $2$. Ia akan menyamai atau melampaui anggota $2$ dan anggota $5$. Kebahagiaannya adalah $2$ satuan, dan keuntungan bersihnya adalah $2 - 1 = 1$ satuan.
• Jika anggota $1$ mengeluarkan $2$ satuan usaha, keahliannya menjadi $3$. Ia akan menyamai atau melampaui anggota $2$, $3$, dan $5$. Kebahagiaannya adalah $3$ satuan, dan keuntungan bersihnya adalah $3 - 2 = 1$ satuan.

Anggota lainnya memiliki potensi maksimum $0$. Oleh karena itu, total potensi untuk hari ke-$5$ adalah $1$.

Pada hari ke-$8$, terdapat $8$ anggota dengan tingkat keahlian $[1, 2, 3, 1, 2, 3, 2, 3]$. Usaha optimalnya adalah $[2, 1, 0, 2, 1, 0, 1, 0]$ dan potensi maksimum yang bersesuaian adalah $[4, 2, 0, 2, 1, 0, 0, 0]$.