시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2.002 초 | 1024 MB | 2 | 2 | 2 | 100.000% |
Петя играет с друзьями в игру, которую иногда называют <<Жребий Крижановского>>. Правила игры следующие: в каждом туре каждый игрок загадывает произвольное натуральное число. После этого игрок, загадавший минимальное число, которое не повторяется, выигрывает в этом туре, причем его выигрыш равен этому числу. Например, если играют 6 человек и были загаданы числа 3, 2, 1, 1, 4 и 2, то выиграл первый игрок, причем его выигрыш равен 3. Если все загаданные числа повторяются, то тур считается ничейным и никто баллов не получает.
Общий выигрыш игрока за игру равен сумме баллов за все сыгранные туры.
Петя с друзьями при игре просто называют по очереди загаданные ими числа, а потом определяют, кто выиграл, и подсчитывают баллы. Однако при таком формате игры в принципе можно сжульничать, не загадывая число заранее, а, уже зная числа, названные предыдущими игроками, выбрать себе оптимальное <<загаданное>> число. Этим и пользуется Петя. Он называет число последним и старается выбрать число так, чтобы максимизировать свой выигрыш.
Идет последний тур игры. Известны очки всех игроков перед этим туром и названные игроками числа. Выясните, какое число следует назвать Пете, чтобы по результатам игры у как можно большего числа игроков количество баллов было меньше чем у него. Если таких чисел несколько, то Петя хочет назвать минимальное возможное.
Первая строка входного файла содержит число $n$ --- количество игроков ($2 \le n \le 100$). Вторая строка содержит $n$ чисел --- баллы игроков перед последним туром (неотрицательные целые числа, не большие 100). Баллы перечислены в том порядке, в котором игроки обычно называют числа (то есть Петины баллы указаны последними). Третья строка содержит $n - 1$ число --- числа, названные игроками в последнем туре (числа не превышают 100), в том порядке, в котором они их называли.
Выведите в выходной файл число, которое следует назвать Пете.
6 0 0 0 0 0 0 2 3 4 5 6
1
6 8 3 12 5 0 9 2 1 3 1 4
2
Во втором примере Петя не может выиграть в последнем туре. Однако, назвав число 2, Петя не позволяет выиграть первому игроку, и тем самым остается вторым по итогам всей игры. У четырех игроков баллы меньше чем у Пети.