高斯消元

问题描述

everlasting 觉得太无聊了，于是决定自己玩游戏！ 他拿出了$n$ 个小圆，第 $i$ 个的颜色是 $a_i$。

接着他将这 $n$ 个小圆复制 $m$ 次并依次连接起来。之后他发现其中有很多颜色相同的小圆，于是他决定：每有k个连续颜色相同的小圆就将他们消去，并将剩下的依次连接。（注意只会消除 $k$ 个，即使有超过 $k$ 个）他将每次从头开始不断进行这个操作直到无法操作为止。他想知道最后能剩下多少个小圆？

输入格式

从文件 $guass.in$ 中输入数据。

第一行三个正整数 $n,m,k$，表示开始小圆的个数，复制次数和消除连续小圆的个数。

第二行 $n$ 个正整数，第 $i$ 个数表示第 $i$ 个小圆的颜色。

输出格式

输出到文件 $guass.out$ 中。

一个整数，表示剩余小圆的个数。

样例 1 输入

4 5 2
1 2 3 1

样例 1 输出

12

样例 1 解释

原来的顺序是1 2 3 1 1 2 3 1 1 2 3 1 1 2 3 1 1 2 3 1，共删掉 $8$ 个 $1$ ，剩余 $12$ 个。

样例 2 输入

1 9 2
1

样例 2 输出

1

样例 2 解释

剩余 $1$ 个 $1$。

样例 3 输入

3 10 2
1 2 1

样例 3 输出

0

样例 3 解释

注意新形成的连续k个小圆也会消除。

数据规模与约定

测试点编号	$n的范围$	$m的范围$	$k的范围$	$a_i的范围$	其他性质
1	$=1$	$=1$	$< 10^9$	$<10^9$
2	$=1$	$\leq 10^5$	$\leq 10^9$	$\leq 10^9$
3	$\leq 10^3$	$\leq 10^3$	$=2$	$=1$
4	$\leq 10^3$	$\leq 10^3$	$=2$	$\leq 10^9$
5	$\leq 10^3$	$=1$	$\leq 10$	$\leq 10^9$
6	$\leq 10^3$	$=2$	$\leq 10^9$	$\leq 2$
7	$\leq 10^3$	$\leq 10^3$	$\leq 10^9$	$\leq 10^9$
8	$\leq 10^3$	$\leq 10^5$	$\leq 10^5$	$\leq 2$	$所有a_i相等$
9	$\leq 10^3$	$\leq 10^5$	$=2$	$\leq 10^9$
10	$\leq 10^3$	$\leq 10^9$	$\leq 10$	$\leq 10^9$	$a_i单调递增$
11	$\leq 10^3$	$\leq 10^9$	$\leq 10^3$	$\leq 10^9$	$所有 a_i相等$
12	$\leq 10^3$	$\leq 10^9$	$\leq 10^9$	$\leq 10^9$
13	$\leq 10^5$	$=1$	$\leq 10^9$	$\leq 10^9$
14	$\leq 10^5$	$=2$	$\leq 10^9$	$\leq 10^9$
15	$\leq 10^5$	$=3$	$\leq 10^9$	$\leq 10^9$
16	$\leq 10^5$	$\leq 10^9$	$=2$	$\leq 2$
17	$\leq 10^5$	$\leq 10^9$	$\leq 10^9$	$\leq 2$	$a_i单调递增$
18	$\leq 10^5$	$\leq 10^9$	$=2$	$\leq 10^9$
19	$\leq 10^5$	$\leq 10^9$	$\leq 10^9$	$\leq 10^9$
20	$\leq 10^5$	$\leq 10^9$	$\leq 10^9$	$\leq 10^9$