Божевільна бабуся#7479

Божевільна бабуся

1 секунда

128 мегабайтів

Середня

Наступне завдання є варіацією відомої головоломки з теорії ймовірностей. У літаку є $n$ місць, і всі вони продані пасажирам. Пасажири заходять по одному, у порядку своїх місць, від $1$ до $n$ (пасажир з номером місця $1$ заходить першим, потім пасажир з номером місця $2$ , і так далі).

Як ви вже здогадалися, божевільні бабусі ненавидять черги і правила, тому вони зазвичай йдуть попереду всіх і заходять першими (незважаючи на те, що у них може не бути першого місця). Вони займають будь-яке місце, яке їм подобається (випадково, може вийти так, що вони оберуть своє власне місце).

Після того, як бабуся зайняла місце, наступні пасажири заходять у порядку їх місць (як описано вище) і розсаджуються наступним чином:

якщо його/її місце вільне, то він/вона займає своє місце;
але якщо його/її місце вже зайняте, він/вона займає будь-яке з решти вільних місць.

Яке місце дістанеться останньому пасажиру? Відповідь проста: останній пасажир сяде або на своє місце, або на місце божевільної бабусі!

Припустимо, що божевільна бабуся займає місце $j$ , яке не є її власним. Коли зайде пасажир, якому було призначено місце $j$ , він/вона займає якесь із вільних місць. Ця ситуація може повторитися з наступними пасажирами. Але коли якийсь пасажир сяде на місце божевільної бабусі, очевидно, всі наступні пасажири сядуть на свої власні місця. У цьому завданні ми хотіли б дізнатися початкове місце божевільної бабусі.

Вхідні дані

Містить декілька тестів. Перший рядок містить ціле число $t$ ( $1 \leq t \leq 10$ 1 \leq t \leq 10) тестів. Кожен з наступних $t$ рядків містить $n + 1$ n + 1 чисел, розділених пробілом: спочатку $n$ ( $1 \leq n \leq 1 0^{3}$ 1 \leq n \leq 10^3), далі $n$ чисел, які представляють місця, зайняті пасажирами у порядку їх входу ( $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n - де $p_{i}$ p_i означає, що пасажир, який зайшов $i$ -им, зайняв місце $p_{i}$ p_i). Гарантується, що вхідні дані правильні, тобто задовольняють умовам задачі.

Вихідні дані

Виведіть місце божевільної бабусі, якщо воно може бути визначено однозначно, в іншому випадку, виведіть $0$ .

Приклади

Приклад 1

Примітка

У випадку 2 2 1 ми не можемо визначити відповідь однозначно, оскільки пасажир $1$ є божевільною бабусею, яка зайняла чуже місце, і пасажир $2$ також може бути божевільною бабусею, яка сіла на своє місце.