HILO (Qızıl)

Besi x + 0.5 sayını bilir, burada x 0 ilə n arasında olan tam ədəddir, hər iki sərhəd daxil olmaqla.

Elza bu sayını tapmağa çalışır. O, 1 ilə n arasında olan bəzi i üçün "sayı i böyükdür ya kiçikdir?" tipli suallar verə bilər. Besi "HI" cavabını verir, əgər i sayı x + 0.5-dən böyükdürsə, və ya "LO" əgər i sayı x + 0.5-dən kiçikdirsə.

Elza sayını taparkən aşağıdakı strategiyaya riayət edir. Əvvəlcə o, 1-dən n-ə qədər olan hər bir ədədin dəqiq bir dəfə rast gəldiyi n ədədlik bir siyahı yaradır (başqa sözlə, bu siyahı n ölçülü bir permutasiyadır). Sonra o, bu siyahı üzrə ardıcıllıqla suallar verir.

Lakin Elza faydasız sualları atlayır, məsələn, əgər Elza indi i sayını soruşmalıdırsa və əvvəlcə j < i sayını soruşub və Besi "HI" cavabını veribsə, Elza i sayını soruşmur və siyahıdakı növbəti sayıya keçir. Eyni şəkildə, əgər o, əvvəlcə j > i sayını soruşub və "LO" cavabını alıbsa, Elza i sayını soruşmur və siyahıdakı növbəti sayıya keçir. Bu strategiyaya riayət edərək, Elza hər zaman x-i dəqiq müəyyən edəcək, hansı permutasiyanı yaratmasından asılı olmayaraq.

Əgər biz Besinin "HI" və ya "LO" cavablarını bir sıraya s birləşdiririksə, onda Besinin "HILO" dediyi hallar s sıradakı uzunluğu 4 olan və "HILO"-ya bərabər olan alt sıraların sayıdır.

Besi Elzanın strategiyasını bilir; daha da əhəmiyyətlisi, o, Elzanın istifadə edəcəyi dəqiq permutasiyanı da bilir. Lakin Besi hələ hansı x sayını istifadə edəcəyinə qərar verməyib.

Besiyə hər bir x dəyəri üçün neçə dəfə "HILO" deyəcəyini müəyyən etməyə kömək edin.

Giriş Məlumatları

Birinci sətir n (1 ≤ n ≤ 2 * 10^5) ehtiva edir.

İkinci sətir Elzanın n ölçülü permutasiyasını ehtiva edir.

Çıxış Məlumatları

0-dan n-ə qədər olan hər bir x üçün, ayrı-ayrı sətirlərdə Besinin neçə dəfə "HILO" deyəcəyini yazın.

Nümunə

x = 0 üçün, Besi "HIHI" deyəcək - 0 dəfə.

x = 2 üçün, Besi "HILOLOHIHI" deyəcək - bir dəfə "HILO".

x = 3 üçün, Besi "HILOLOHILO" deyəcək - iki dəfə "HILO".