← 返回题目列表

Codeforces · 878/B

B. 团队组建

中文机器翻译题面 查看原题

这次伯兰信息学团体奥林匹克竞赛在一个只有一辆小巴士才能到达的偏远城市举行。公共汽车有n个乘客座位,座位i只能由来自ai城市的参与者占据。

今天,巴士已完成 m 次行程,每次搭载 n 名参与者。然后,参与者按照到达的顺序排成一排,来自同一辆公共汽车的人按照座位顺序站立(即,如果我们写下参与者来自的城市,我们会得到序列 a1,a2,...,重复 m 次)。

之后组成一些队伍,每队由 k 名参赛者组成,组成同一城市,并排排列。一旦形成,团队就离开队伍。组队直至没有来自同一城市的 k 个相邻参赛者。

帮助组织者确定该流程结束后队列中还剩下多少参与者。我们可以证明这个答案并不取决于球队选择的顺序。

输入

第一行包含三个整数 n、k 和 m (1 ≤ n ≤ 105、2 ≤ k ≤ 109、1 ≤ m ≤ 109)。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 105),其中 ai 是城市号,乘客必须在公交车上坐在 i 上。

输出

输出队列中剩余参与者的数量。

示例

输入 #1

4 2 5
1 2 3 1

输出 #1

12

输入 #2

1 9 10
1

输出 #2

1

输入 #3

3 2 10
1 2 1

输出 #3

0

注意

在第二个示例中,队伍由来自同一城市的 10 名参与者组成。他们九人将组成一个团队。最后,只有一名参与者会留在队伍中。