Şüşə muncuqlar#2912

Şüşə muncuqlar

1 saniyə

10 meqabayt

Çox asan

Bir zamanlar məşhur bir aktrisa vardı. Gözlədiyiniz kimi, o ən çox Qədim Komediyalarda çıxış etməyi sevirdi. Hamı onu çox istəyirdi, amma o, izdihamlarla maraqlanmırdı. Onun ən böyük hobbisi hər cür muncuqlar toplamaq idi. Bir çox muncuq ustası onun üçün işləyirdi, hər gün yeni boyunbağılar və bilərziklər düzəldirdilər. Bir gün o, əsas Muncuq Ustaları İnspektorunu (MUI) çağırdı və ondan çox uzun və xüsusi bir boyunbağı istədiyini bildirdi.

Boyunbağı şüşə muncuqlardan hazırlanmalı idi, hər biri müxtəlif ölçüdə, bir-birinə birləşdirilmişdi, amma muncuqlardan heç birinin içindən ip keçmirdi—belə ki, hər bir muncuq istənilən anda ayrıla bilərdi. Aktrisa istədiyi muncuqlar ardıcıllığını seçdi, və MUI boyunbağını düzəltməyə söz verdi. Amma sonra bir problem ortaya çıxdı: iki qonşu muncuq arasındakı birləşmə çox da etibarlı deyildi, buna görə boyunbağı öz ağırlığından qopa bilərdi. Əgər boyunbağı ayrılsa vəziyyət daha da pis olardı. Muncuq birləşdirilən nöqtələr çox vacibdir. Əgər kiçik muncuqlar başlanğıcdadırsa, qırılma ehtimalı, böyük muncuqlar olsaydı olduğundan daha yüksəkdir. Muncuq ustası boyunbağının etibarlılığını yoxlamaq istəyir və boyunbağının ən pis ayrılma nöqtəsini müəyyən edən bir proqram tələb olunur.

Boyunbağı, $A = a_{1} a_{2} \dots a_{m}$ A = a_1a_2\ldots a_m sətri ilə təsvir olunur; burada boyunbağının konkret muncuqlarının ölçüləri verilir; boyunbağı dairəvidir, yəni $a_{m}$ a_m muncuğundan sonra $a_{1}$ a_1 gəlir.

$i$ mövqeyindəki birləşmə yalnız və yalnız $A [i] = a_{i} a_{i + 1} \dots a_{m} a_{1} \dots a_{i - 1}$ A[i] = a_i a_{i+1} \ldots a_m a_1 \ldots a_{i-1} sətri leksikoqrafik olaraq $A [j] = a_{j} a_{j + 1} \dots a_{m} a_{1} \dots a_{j - 1}$ A[j] = a_j a_{j+1} \ldots a_m a_1 \ldots a_{j-1} sətrindən kiçikdirsə, $j$ mövqeyindəki birləşmədən daha pis hesab olunur. $a_{1} a_{2} \dots a_{n}$ a_1 a_2 \ldots a_n sətri $b_{1} b_{2} \dots b_{n}$ b_1 b_2 \ldots b_n sətrindən o zaman leksikoqrafik olaraq kiçik sayılır ki, elə bir $i$ tam ədədi ( $i \leq n$ i \leq n) mövcuddur, $a_{j} = b_{j}$ a_j = b_j bütün $j$ -lər üçün ( $1 \leq j < i$ 1 \leq j < i), və $a_{i} < b_{i}$ a_i < b_i.

Giriş

Birinci sətirdə testlərin sayı $N$ verilir. Hər testin təsviri bir sətirdə verilir, boyunbağının quruluşu göstərilir. Boyunbağının maksimum uzunluğu $10000$ simvoldur. Hər muncuq İngilis əlifbasının kiçik hərfi ( $a$ - $z$ ) ilə təsvir olunur; burada $a < b < \dots < z$ a < b < \ldots < z.

Çıxış

Hər bir test üçün sadəcə bir tam ədəd çıxışa yazın—ən pis ayrılma nöqtəsində birinci gələn muncuğun nömrəsini, yəni, $A [i]$ sətrinin bütün $n$ mümkün ayrılmalar arasında leksikoqrafik olaraq ən kiçik olduğu ən kiçik $i$ indeksini çıxışa verin. Əgər bir neçə həll mümkündürsə, ən kiçik $i$ olanı çap edin.

Nümunələr

Nümunə 1