Задача №112798. Locksmith
Семён недавно устроился работать ключником в отель. Для начала он хочет продемонстрировать свои навыки работы. Начальник ключников дал Семёну большое кольцо и N, насаженных на него, ключей, завязал ему глаза и отправил в большую комнату. В комнате N дверей. Каждый ключ открывает ровно одну дверь.
Его работа открывать и закрывать каждую дверь снова и снова. Семён идёт вдоль стены всегда в одном направлении и, нащупав дверь, пытается открыть её. Он перебирает ключи на кольце слева направо, и если ключ не подошёл, то Семён отправляет его в другой конец кольца.
Семён не знал, что начальник проверяет его выносливость, ведь комната была круглой. Поэтому, открыв и закрыв последнюю дверь, он приступает к первой. Но Семён оказался работящим и стойким парнем, поэтому он работал часами, не сказав ни единого слова. И только открыв и закрыв K-ую дверь он сказал: "Если бы я знал, сколько раз я вставлял в замочную скважину неправильный ключ!"
Ваша задача ответить на этот вопрос!
В первой строке даны два числа: 1 ≤ N ≤ 105, 1 ≤ K ≤ 109. Следующие N строк содержат по одному числу vi, означающее, что i-ый ключ открывает дверь vi.
Вывести ответ на вопрос Семёна.
Первая подзадача, оценивается в 40 баллов: 1 ≤ N, K ≤ 1000.
Вторая подзадача, оценивается в 60 баллов: 1 ≤ K ≤ 50000.
3 5 1 2 3
4
4 6 4 2 1 3
13
10 7 1 3 2 4 5 7 6 8 9 10
25