Teams Formation

이번 정보학 Berland Team Olympiad은 작은 버스 한 대로만 갈 수 있는 외딴 도시에서 열린다. 버스에는 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번 좌석에 앉아야 하는 사람이 온 도시의 번호이다.

줄에 남은 참가자 수를 출력한다.

두 번째 예제에서 줄은 같은 도시 출신 참가자 열 명으로 구성된다. 그중 아홉 명이 팀을 이룬다. 마지막에는 참가자 한 명만 줄에 남는다.