Задача D. Лотерея Амидакудзи ≡

Условие

Амидакудзи (яп. «лотерея Амиды») — японский метод лотереи, позволяющий быстро распределить некоторые предметы между её участниками. Амидакудзи используется, чтобы распределить вещи среди людей, когда количество распределяемых вещей равно числу людей. Например, работа по дому или призы могут быть справедливо и случайным образом распределены при помощи такой лотереи.

Амидакудзи состоит из так называемых «лесенок», в которых число вертикальных линий равно числу участников и вещей, а горизонтальные располагаются в случайном порядке.

Правила игры: необходимо выбрать линию в верхней части и следовать за этой линией вниз. При столкновении с горизонтальной нужно повернуть на соседнюю линию и следовать уже по ней. Таким образом нужно следовать вниз, пока линии не кончатся. Под линиями обозначены различные «призы», которые достигшие нижнего уровня и получают.

Определите, какую вертикальную линию следует выбрать, чтобы получить приз под порядковым номером x?

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n — количество вертикальных линий и k — количество горизонтальных линий. Во второй строке через пробел расположено k натуральных чисел a_i — описание горизонтальных линий, перечисленных в порядке сверху вниз (все линии расположены на разной высоте). Если a_i = p, это значит, что горизонтальная линия соединяет вертикальные линии под номерами p и p + 1. В третьей строке расположено натуральное число x — выбранный участником номер приза.

Формат выходных данных

Выведите одно натуральное число — порядковый номер вертикальной линии, которую следует выбрать участнику.

Ограничения

1 ≤ x ≤ n ≤ 10⁵

1 ≤ k ≤ 10⁵

1 ≤ a_i ≤ n − 1

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n = 2, получат не менее 10 баллов.

Пояснение к примеру

Смотри рисунок. В примере дано n = 7 вертикальных линий и k = 9 горизонтальных линий. Участник, выбравший четвертую вертикальную линию пройдет по маршруту красной линии и получит приз под пятым номером.

Примеры тестов

7 9
3 1 2 4 6 5 2 3 4
5

4