| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 12 | 8 | 7 | 63.636% |
Тор, Ракета и Грут ходят по торговому центру и выбирают ресторан, в котором они поужинают. У каждого из них свои предпочтения, Тору нравятся рестораны с большим выбором стейков, Ракете нравятся бургеры, а Грут предпочитает пиццу. Так или иначе, каждый из них выставил все рестораны (с номерами от $1$ до $n$) в порядке своих приоритетов.
Как же им выбрать ресторан? Будет неловко, если они пойдут в какой-то ресторан, а кафе напротив будет более предпочтительно и у Ракеты, и у Грута. А кафе может оказаться хуже другой забегаловки по мнению Тора и Ракеты... Они решили выбрать ресторан, который не будет уступать никакому другому ресторану.
Более формально, нужно найти такой ресторан, что любой другой ресторан будет менее предпочтителен у не менее чем двух Мстителей. Помогите им найти такой ресторан, или скажите что его не существует.
В первой строке содержится $n$ --- число ресторанов ($1 \le n \le 100\,000$).
Во второй строке содержится перестановка чисел от $1$ до $n$ --- список ресторанов в порядке предпочтения у Тора, от более предпочтительного к менее предпочтительному.
В третьей строке в аналогичном формате записаны предпочтения Ракеты, а в четвертой строке --- предпочтения Грута.
Выведите номер самого лучшего ресторана, или $-1$, если его не существует.
3 1 2 3 2 3 1 3 1 2
-1
4 2 1 3 4 3 1 4 2 4 1 2 3
1