Божевільна бабуся
Наступне завдання є варіацією відомої головоломки з теорії ймовірностей. У літаку є n місць, і всі вони продані пасажирам. Пасажири заходять по одному, у порядку своїх місць, від 1 до n (пасажир з номером місця 1 заходить першим, потім пасажир з номером місця 2, і так далі).
Як ви вже здогадалися, божевільні бабусі ненавидять черги і правила, тому вони зазвичай йдуть попереду всіх і заходять першими (незважаючи на те, що у них може не бути першого місця). Вони займають будь-яке місце, яке їм подобається (випадково, може вийти так, що вони оберуть своє власне місце).
Після того, як бабуся зайняла місце, наступні пасажири заходять у порядку їх місць (як описано вище) і розсаджуються наступним чином:
якщо його/її місце вільне, то він/вона займає своє місце;
але якщо його/її місце вже зайняте, він/вона займає будь-яке з решти вільних місць.
Яке місце дістанеться останньому пасажиру? Відповідь проста: останній пасажир сяде або на своє місце, або на місце божевільної бабусі!
Припустимо, що божевільна бабуся займає місце j, яке не є її власним. Коли зайде пасажир, якому було призначено місце j, він/вона займає якесь із вільних місць. Ця ситуація може повторитися з наступними пасажирами. Але коли якийсь пасажир сяде на місце божевільної бабусі, очевидно, всі наступні пасажири сядуть на свої власні місця. У цьому завданні ми хотіли б дізнатися початкове місце божевільної бабусі.
Вхідні дані
Містить декілька тестів. Перший рядок містить ціле число t (1 ≤ t ≤ 10) тестів. Кожен з наступних t рядків містить n + 1 чисел, розділених пробілом: спочатку n (1 ≤ n ≤ 10^3), далі n чисел, які представляють місця, зайняті пасажирами у порядку їх входу (p[1], p[2], ..., p[n] - де p[i] означає, що пасажир, який зайшов i-им, зайняв місце p[i]). Гарантується, що вхідні дані правильні, тобто задовольняють умовам задачі.
Вихідні дані
Виведіть місце божевільної бабусі, якщо воно може бути визначено однозначно, в іншому випадку, виведіть 0.
Примітка
У випадку 2 2 1 ми не можемо визначити відповідь однозначно, оскільки пасажир 1 є божевільною бабусею, яка зайняла чуже місце, і пасажир 2 також може бути божевільною бабусею, яка сіла на своє місце.