Teams Formation
Contest: Codeforces Round 443 (Div. 1)
Difficulty rating: 2300
Tags: data structures, implementation

This time the Berland Team Olympiad in Informatics is held in a remote city that can only be reached by one small bus. Bus has n passenger seats, seat i can be occupied only by a participant from the city ai.

Today the bus has completed m trips, each time bringing n participants. The participants were then aligned in one line in the order they arrived, with people from the same bus standing in the order of their seats (i. e. if we write down the cities where the participants came from, we get the sequence a1, a2, ..., an repeated m times).

After that some teams were formed, each consisting of k participants form the same city standing next to each other in the line. Once formed, teams left the line. The teams were formed until there were no k neighboring participants from the same city.

Help the organizers determine how many participants have left in the line after that process ended. We can prove that answer doesn't depend on the order in which teams were selected.

Input format:
The first line contains three integers n, k and m (1 ≤ n ≤ 105, 2 ≤ k ≤ 109, 1 ≤ m ≤ 109).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105), where ai is the number of city, person from which must take seat i in the bus.

Output format:
Output the number of remaining participants in the line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the second example, the line consists of ten participants from the same city. Nine of them will form a team. At the end, only one participant will stay in the line.

Example input:
4 2 5
1 2 3 1

Example output:
12

Example input:
1 9 10
1

Example output:
1

Editorial:
First, let's see what happens inside one bus. We can use a stack containing pairs (city, number of participants from it). When the number of participants reaches k, we erase the pair.
Suppose we build this stack. r is its size, (ci, di) are pairs in it. Now consider the interaction of two such buses. At the border, a team is formed, if c1 = cr and d1 + dr ≥ k. If the inequality becomes an equality, then another team can be formed from the second and penultimate groups, etc. Let's find the greatest p such that for each i = 1... p we have ci = cr + 1 - i and di + dr + 1 - i = k. Since the condition on i is symmetric with respect to $$\hat{i}\mapsto r+1-\hat{i}$$, if p ≥ ⌈ r / 2⌉, then p = r.
Consider the case p = r separately. This means that the two buses are completely divided into teams. If m is even, answer is zero, otherwise answer is the sum of di.
Also, consider the case when r is odd and p = ⌊ r / 2⌋. In this case, after removing all teams at the borders of the buses, the queue looks like: left part of the first bus — mdp + 1 people from the cp + 1 city — right part of the last bus. If the number of people in the middle is divisible by k, then they will be divided into the commands, and the first half will unite with the last, and the answer is zero. If it doesn't, then some teams will be formed in the middle, and the process will end there.
Finally, if r is even smaller, it can be seen that after the formation of teams at the borders of buses the process will end.