Saç kəsimi

Fermer Con inadkar saçlarından bezərək saçını kəsdirməyə qərar verdi. Onun n saç teli bir sıra halında düzülüb və i teli ilkin olaraq a[i] mikrometr uzunluğundadır. O, saçlarının uzunluğunun monoton şəkildə artmasını istəyir, buna görə də saçlarının "pis görünüşünü" inversiyaların sayı kimi müəyyən edir: (i, j) cütləri elə ki, i < j və a[i] > a[j].

Hər bir j = 0, 1, ..., n − 1 üçün Con bilmək istəyir ki, əgər uzunluğu j-dən böyük olan bütün tellər dəqiq j uzunluğuna qədər qısaldılsa, saçlarının pis görünüşü nə qədər olacaq.

(Maraqlı fakt: orta insan başında həqiqətən təxminən 10^5 saç teli var!)

Giriş məlumatları

Birinci sətir n (1 ≤ n ≤ 10^5) ədədini ehtiva edir. İkinci sətir a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ n) ədədlərini ehtiva edir.

Çıxış məlumatları

Hər bir j = 0, 1, ..., n − 1 üçün Conun saçlarının pis görünüşünü ayrı-ayrı sətirlərdə çıxarın. Qeyd edək ki, bu məsələdə böyük tam ədədlərin ölçüsü 64-bitlik tam ədəd tiplərinin (məsələn, C/C++-da long long) istifadəsini tələb edə bilər.

Nümunə

Dördüncü çıxış sətiri Conun saçları 3 uzunluğuna qədər qısaldıldıqda inversiyaların sayını təsvir edir. O zaman A = [3, 2, 3, 3, 0] beş inversiyaya malikdir: a[1] > a[2], a[1] > a[5], a[2] > a[5], a[3] > a[5] və a[4] > a[5].