Dəli qarı
Növbəti tapşırıq ehtimal nəzəriyyəsindən tanınmış bir tapmacanın variasiyasıdır. Təyyarədə n yer var və bütün yerlər sərnişinlərə satılıb. Sərnişinlərə öz yerlərinin sırasına görə, 1-dən n-ə qədər (yer nömrəsi 1 olan sərnişin birinci daxil olur, sonra yer nömrəsi 2 olan sərnişin daxil olur və s.) daxil olmaq təklif edilir.
Artıq təxmin etdiyiniz kimi, dəli qocalar növbələri və qaydaları sevmirlər, buna görə də onlar adətən hamıdan əvvəl gedir və birinci daxil olurlar (onların birinci yeri olmasa belə), üstəlik, onlar istədikləri hər hansı bir yeri tuturlar (təsadüfi olaraq, öz yerlərini də seçə bilərlər).
Qoca bir yer tutduqdan sonra, növbəti sərnişinlər öz yerlərinin sırasına görə daxil olur (yuxarıda təsvir edildiyi kimi) və aşağıdakı kimi otururlar:
əgər onun yeri boşdursa, o, öz yerini tutur.
lakin əgər onun yeri artıq tutulubsa, o, qalan yerlərdən birini tutur.
Sonuncu sərnişinə hansı yer düşəcək? Cavab sadədir: sonuncu sərnişin ya öz yerində, ya da dəli qocanın yerində oturacaq!
Tutaq ki, dəli qoca öz yeri olmayan j yerini tutur. j yerinə təyin olunmuş sərnişin daxil olduqda, o, boş yerlərdən birini tutur. Bu vəziyyət növbəti sərnişinlərlə təkrarlana bilər. Amma hansısa sərnişin dəli qocanın yerində oturduqda, açıq-aşkar (!) bütün növbəti sərnişinlər öz yerlərində oturacaqlar. Bu tapşırıqda biz dəli qocanın ilkin yerini öyrənmək istəyirik.
Giriş məlumatları
Bir neçə testdən ibarətdir. Birinci sətir t (1 ≤ t ≤ 10) testlərinin tam ədədini ehtiva edir. Növbəti t sətirin hər biri n + 1 ədəd ehtiva edir, əvvəlcə n (1 ≤ n ≤ 10^3), sonra isə sərnişinlərin daxil olma sırasına görə tutduqları yerlər (p[1], p[2], ..., p[n] - burada p[i] sərnişinin i-ci daxil olduğu yeri göstərir). Giriş məlumatlarının düzgün olduğu, yəni tapşırığın şərtlərinə uyğun olduğu təmin edilir.
Çıxış məlumatları
Əgər dəli qocanın yeri birmənalı olaraq müəyyən edilə bilirsə, onu çıxarın, əks halda 0 çıxarın.
Qeyd
2 2 1 halında cavabı birmənalı olaraq müəyyən edə bilmirik, çünki 1 nömrəli sərnişin öz yerində oturmuş dəli qoca ola bilər və 2 nömrəli sərnişin də öz yerində oturmuş dəli qoca ola bilər.