B. Составление команд
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этот раз Берляндская командная олимпиада по информатике проводится в отдалённом городке, куда ходит лишь один небольшой автобус. В нём есть n пассажирских мест, каждое из которых занято за одним из участвующих городов, то есть место i может занять только участник из города ai.

Сегодня автобус сделал m рейсов, каждый раз привозя n участников. Участников выстроили в очередь в порядке прибытия, люди из одного автобуса встают в очередь в том порядке, в котором они занимали места в автобусе. Так, если мы выпишем города, из которых прибыли участники в очереди, мы получим последовательность a1, a2, ..., an, повторенную m раз.

После прибытия всех рейсов участники начинают объединяться в команды. Если в очереди стоят k человек подряд из одного города, они собирают команду и выходят из очереди. Команды образовываются в произвольном порядке, пока есть k человек подряд из одного города.

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

Входные данные

В первой строке содержатся числа n, k и m, разделённые пробелом (1 ≤ n ≤ 105, 2 ≤ k ≤ 109, 1 ≤ m ≤ 109).

Следующая строка содержит n чисел a1, a2, ..., an (1 ≤ ai ≤ 105), где ai — номер города, представитель которого должен занять место i в автобусе.

Выходные данные

Выведите одно число — количество оставшихся в очереди участников.

Примеры
Входные данные
4 2 5
1 2 3 1
Выходные данные
12
Входные данные
1 9 10
1
Выходные данные
1
Входные данные
3 2 10
1 2 1
Выходные данные
0
Примечание

Во втором примере очередь состоит из десяти участников из одного города. Девять из них образуют команду. В конце в очереди будет стоять лишь участник.