| Автор: | Восьмая всероссийская командная олимпиада школьников по программированию | Ограничение времени: | 2 сек | |
| Входной файл: | game.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | game.out |
Петя играет с друзьями в игру, которую иногда называют "Жребий Крижановского". Правила игры следующие: в каждом туре каждый игрок загадывает произвольное натуральное число. После этого игрок, загадавший минимальное число, которое не повторяется, выигрывает в этом туре, причем его выигрыш равен этому числу. Например, если играют 6 человек и были загаданы числа 3, 2, 1, 1, 4 и 2, то выиграл первый игрок, причем его выигрыш равен 3. Если все загаданные числа повторяются, то тур считается ничейным и никто баллов не получает.
Петя с друзьями при игре просто называют по очереди загаданные ими числа, а потом определяют, кто выиграл, и подсчитывают баллы. Однако при таком формате игры в принципе можно сжульничать, не загадывая число заранее, а, уже зная числа, названные предыдущими игроками, выбрать себе оптимальное "загаданное" число. Этим и пользуется Петя. Он называет число последним и старается выбрать число так, чтобы максимизировать свой выигрыш.
Идет последний тур игры. Известны очки всех игроков перед этим туром и названные игроками числа. Выясните, какое число следует назвать Пете, чтобы по результатам игры у как можно большего числа игроков количество баллов было меньше чем у него. Если таких чисел несколько, то Петя хочет назвать минимальное возможное.
Общий выигрыш игрока за игру равен сумме баллов за все сыгранные туры.
Первая строка входного файла содержит число n — количество игроков. Вторая строка содержит n чисел — баллы игроков перед последним туром (неотрицательные целые числа, не большие 100). Баллы перечислены в том порядке, в котором игроки обычно называют числа (то есть Петины баллы указаны последними). Третья строка содержит n − 1 число — числа, названные игроками в последнем туре (числа не превышают 100), в том порядке, в котором они их называли.
Выведите в выходной файл число, которое следует назвать Пете.
Во втором примере Петя не может выиграть в последнем туре. Однако, назвав число 2, Петя не позволяет выиграть первому игроку, и тем самым остается вторым по итогам всей игры. У четырех игроков баллы меньше чем у Пети.
2 ≤ n ≤ 100
| № | Входной файл (game.in) |
Выходной файл (game.out) |
|---|---|---|
| 1 | |
|
| 2 | |
|