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 _a__i_.
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 _a_1, _a_2, ..., _a__n_ 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
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 _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 105), where _a__i_ is the number of city, person from which must take seat _i_ in the bus.
## Output
Output the number of remaining participants in the line.
[samples]
## 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.
这次，贝尔兰信息学团队奥林匹克竞赛在一座偏远城市举行，该城市只能通过一辆小型巴士到达。巴士有 #cf_span[n] 个乘客座位，第 #cf_span[i] 个座位只能由来自城市 #cf_span[ai] 的参赛者乘坐。
今天，这辆巴士已经完成了 #cf_span[m] 次行程，每次带来 #cf_span[n] 名参赛者。参赛者们按到达顺序排成一列，同一辆巴士上的人员按座位顺序排列（即，如果我们写下参赛者来自的城市，会得到序列 #cf_span[a1, a2, ..., an] 重复 #cf_span[m] 次）。
之后，组织者开始组建队伍，每个队伍由来自同一城市且在队列中相邻的 #cf_span[k] 名参赛者组成。一旦组成队伍，这些队伍就会离开队列。这个过程持续进行，直到队列中不再存在 #cf_span[k] 个来自同一城市的相邻参赛者。
请帮助组织者确定该过程结束后，队列中剩余的参赛者人数。我们可以证明，答案与队伍选择的顺序无关。
第一行包含三个整数 #cf_span[n, k] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 105]，#cf_span[2 ≤ k ≤ 109]，#cf_span[1 ≤ m ≤ 109]）。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]），其中 #cf_span[ai] 表示必须坐在巴士第 #cf_span[i] 个座位上的参赛者来自的城市编号。
请输出队列中剩余的参赛者人数。
在第二个示例中，队列由十名来自同一城市的参赛者组成。其中九人将组成一个队伍。最终，队列中仅剩一名参赛者。
## Input
第一行包含三个整数 #cf_span[n, k] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 105]，#cf_span[2 ≤ k ≤ 109]，#cf_span[1 ≤ m ≤ 109]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]），其中 #cf_span[ai] 表示必须坐在巴士第 #cf_span[i] 个座位上的参赛者来自的城市编号。
## Output
请输出队列中剩余的参赛者人数。
[samples]
## Note
在第二个示例中，队列由十名来自同一城市的参赛者组成。其中九人将组成一个队伍。最终，队列中仅剩一名参赛者。
**Definitions**
Let $ n, k, m \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 10^5 $, $ 2 \leq k \leq 10^9 $, $ 1 \leq m \leq 10^9 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of city identifiers, where $ a_i \in \mathbb{Z}^+ $, $ 1 \leq a_i \leq 10^5 $.
The full line is the concatenation of $ m $ copies of $ A $, denoted $ A^m $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 2 \leq k \leq 10^9 $
3. $ 1 \leq m \leq 10^9 $
4. $ 1 \leq a_i \leq 10^5 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Simulate the iterative removal of contiguous blocks of $ k $ participants from the same city until no such block remains.
Let $ L $ be the final length of the line after all possible removals.
Compute $ L $.
**Key Insight**
The process is deterministic and order-independent. Define $ f(S) $ as the result of repeatedly removing contiguous runs of length $ k $ from sequence $ S $ until none remain.
We are to compute $ f(A^m) $.
Let $ B $ be the compressed representation of $ A $: a sequence of (city, count) pairs for maximal contiguous runs in $ A $.
Let $ C $ be the compressed representation of $ A^m $, derived from $ B $, accounting for concatenation of $ m $ copies.
The removal process reduces each maximal run of identical city participants of length $ \ell $ to $ \ell \bmod k $.
However, adjacent runs of the same city after removal may merge across copy boundaries.
Let $ r $ be the number of times the first and last elements of $ A $ are the same.
If $ A $ starts and ends with the same city, then concatenating $ m $ copies may merge the end of one copy with the start of the next.
Define:
- Let $ \text{prefix} $: length of maximal prefix of $ A $ with constant city $ c $.
- Let $ \text{suffix} $: length of maximal suffix of $ A $ with constant city $ c $.
- If $ \text{prefix} > 0 $, $ \text{suffix} > 0 $, and $ \text{first}(A) = \text{last}(A) = c $, then the merged run in $ A^m $ has length $ \text{prefix} + \text{suffix} + (m-2)\cdot \text{full\_run} $, where $ \text{full\_run} $ is the total count of $ c $ in one copy of $ A $.
Otherwise, runs remain independent across copies.
Let $ R $ be the total length of all maximal runs in $ A $, each reduced modulo $ k $, and then account for merging across copy boundaries if the first and last elements of $ A $ are equal.
**Formal Objective**
Compute:
$$
L = \begin{cases}
\left( \sum_{\text{runs in } A} (\ell \bmod k) \right) \cdot m & \text{if } a_1 \ne a_n \\
\left( \sum_{\text{runs in } A \setminus \text{merged}} (\ell \bmod k) \right) + \left( (\text{prefix} + \text{suffix} + (m-2)\cdot \text{count}_c) \bmod k \right) & \text{if } a_1 = a_n = c
\end{cases}
$$
where $ \text{count}_c $ is the total number of $ c $ in $ A $, and the sum excludes the prefix and suffix runs (already merged).
But more precisely:
Let $ \text{total\_mod} = \sum_{\text{all runs in } A} (\ell \bmod k) $.
Let $ \text{merged\_run} = \text{prefix} + \text{suffix} + (m-2) \cdot \text{count}_c $ if $ a_1 = a_n $, else 0.
Then:
$$
L = \text{total\_mod} \cdot m - (\text{prefix} \bmod k + \text{suffix} \bmod k) \cdot (m-1) + (\text{merged\_run} \bmod k)
$$
But this is messy.
**Simpler Formalization**
Let $ B $ be the compressed form of $ A $: list of runs $ (c_i, \ell_i) $, $ i=1,\dots,r $.
If $ a_1 \ne a_n $:
Then $ A^m $ is $ m $ independent copies of $ B $, and removals are independent.
$$
L = m \cdot \sum_{i=1}^r (\ell_i \bmod k)
$$
If $ a_1 = a_n = c $:
Let $ p $ = length of prefix run of $ c $, $ s $ = length of suffix run of $ c $, $ t $ = total count of $ c $ in $ A $.
Then in $ A^m $, the $ c $-runs merge into one long run of length:
$$
L_c = p + s + (m-2) \cdot t \quad \text{if } m \geq 2
$$
If $ m = 1 $, then $ L_c = t $.
The remaining runs are the internal runs (not prefix/suffix) of $ A $, each reduced mod $ k $, multiplied by $ m $.
So:
Let $ S = \sum_{\text{internal runs}} (\ell_i \bmod k) $ — i.e., sum over runs not involving the first/last city.
Then:
$$
L = m \cdot S + (L_c \bmod k)
$$
If $ m = 1 $, then $ L_c = t $, and $ S = \sum_{i=2}^{r-1} (\ell_i \bmod k) $.
**Final Formal Statement**
Let $ A = (a_1, \dots, a_n) $.
Let $ B = [(c_1, \ell_1), \dots, (c_r, \ell_r)] $ be the run-length encoding of $ A $.
Let $ p = \ell_1 $ if $ c_1 = c_r $, else 0.
Let $ s = \ell_r $ if $ c_1 = c_r $, else 0.
Let $ t = \sum_{i: c_i = c_1} \ell_i $ if $ c_1 = c_r $, else 0.
Let $ S = \sum_{i=1}^r (\ell_i \bmod k) $.
If $ a_1 \ne a_n $:
$$
L = m \cdot S
$$
If $ a_1 = a_n $:
Let $ L_c = \begin{cases}
t & \text{if } m = 1 \\
p + s + (m-2) \cdot t & \text{if } m \geq 2
\end{cases} $
Let $ S' = S - (p \bmod k) - (s \bmod k) $
Then:
$$
L = m \cdot S' + (L_c \bmod k)
$$
Output $ L $.