Задача №113249. Клуб брутальных людей
Степан является участником известного клуба брутальных людей. В этом клубе ведут рейтинг участников, который меняется только во время ежегодных соревнований. Соревнования состоят из m последовательных раундов. В каждом раунде k лучших участников (согласно рейтингу) садятся вокруг стола с луком. После того как они сели, они начинают резать лук, и первый, кто проронит слезу, перемещается на последнюю строчку рейтинга, и раунд заканчивается. Обратите внимание, что рейтинг у каждого участника разный. Во время соревнований ведется протокол, в котором после каждого раунда записывается позиция выбывшего участника, которая была у него в начале раунда (в конце раунда он перемещается на последнюю позицию).
Степан нашел протокол соревнований этого года, но он забыл свою позицию в рейтинге до начала соревнований. Тем не менее он еще помнит свою нынешнюю позицию в рейтинге. Помогите Степану вспомнить его позицию до начала соревнований. Для этого напишите программу, которая поможет Степану определить его позицию до начала соревнований.
В первой строке входного файла записаны три целых числа n , k , m — количество участников клуба, количество участников в одном раунде и количество раундов соответственно. Во второй строке содержится m целых чисел: i -е число a i ( 1 ≤ a i ≤ k ) задает позицию выбывшего участника в соответствующем раунде. В третьей строке записано целое число p ( 1 ≤ p ≤ n ) — позицию Степана после соревнований.
В единственной строке файла выведите единственное число — позицию Степана до начала соревнований.
Задача состоит из четырёх групп:
- 1 ≤ k < n ≤ 1000, 1 ≤ m ≤ 10 000 .(30 баллов)
- 1 ≤ k ≤ 100, k < n ≤ 10 6 , 1 ≤ m ≤ 100 000 .(20 баллов)
- 1 ≤ k ≤ 100, k < n ≤ 10 9 , 1 ≤ m ≤ 100 000 .(20 баллов)
- 1 ≤ k < n ≤ 10 9 , 1 ≤ m ≤ 100 000 .(30 баллов)
В начале соревнований Степан занимал третью позицию. После первого раунда участник с первой строчки опустился на последнюю, поэтому Степан поднялся на одну позицию вверх, то есть на вторую позицию. После второго раунда Степан опустился на последнюю позицию. После третьего раунда он поднялся на одну позицию вверх, то есть на пятую позицию.
6 2 3 1 2 1 5
3