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 ≤ 10^5, 2 ≤ k ≤ 10^9, 1 ≤ m ≤ 10^9).

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5), 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.


-----Examples-----
Input
4 2 5
1 2 3 1

Output
12

Input
1 9 10
1

Output
1

Input
3 2 10
1 2 1

Output
0



-----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.

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
def main():
	(_, k, m) = [int(x) for x in input().split()]
	a = []
	last = ('-1', 0)
	a.append(last)
	for ai in input().split():
		if last[0] == ai:
			last = (ai, last[1] + 1)
			a[-1] = last
		else:
			last = (ai, 1)
			a.append(last)
		if last[1] == k:
			a.pop()
			last = a[-1]
	a.pop(0)
	s1 = 0
	while len(a) > 0 and a[0][0] == a[-1][0]:
		if len(a) == 1:
			s = a[0][1] * m
			r1 = s % k
			if r1 == 0:
				print(s1 % k)
			else:
				print(r1 + s1)
			return
		join = a[0][1] + a[-1][1]
		if join < k:
			break
		elif join % k == 0:
			s1 += join
			a.pop()
			a.pop(0)
		else:
			s1 += join // k * k
			a[0] = (a[0][0], join % k)
			a.pop()
			break
	s = 0
	for ai in a:
		s += ai[1]
	print(s * m + s1)

def __starting_point():
	main()
__starting_point()


r = lambda : list(map(int, input().split()))
(n, k, m) = r()
a = list(r())
stck = []
for i in range(n):
	if len(stck) == 0 or stck[-1][0] != a[i]:
		stck.append([a[i], 1])
	else:
		stck[-1][1] += 1
	if stck[-1][1] == k:
		stck.pop()
rem = 0
(strt, end) = (0, len(stck) - 1)
if m > 1:
	while end - strt + 1 > 1 and stck[strt][0] == stck[end][0]:
		join = stck[strt][1] + stck[end][1]
		if join < k:
			break
		elif join % k == 0:
			rem += join
			strt += 1
			end -= 1
		else:
			stck[strt][1] = join % k
			stck[end][1] = 0
			rem += join // k * k
tr = 0
slen = end - strt + 1
for el in stck[:slen]:
	tr += el[1]
if slen == 0:
	print(0)
elif slen == 1:
	r = stck[strt][1] * m % k
	if r == 0:
		print(0)
	else:
		print(r + rem)
else:
	print(tr * m + rem)


import sys
from collections import deque
input = sys.stdin.readline
(n, k, m) = map(int, input().split())
a = list(map(int, input().split()))
r = a[0]
flag = 0
for i in range(n):
	if r != a[i]:
		flag = 1
		break
if flag == 0:
	print(m * n % k)
	sys.exit()
if k > n:
	print(m * n)
	sys.exit()
curr = a[0]
tmp = 1
que = deque([(a[0], 1)])
for i in range(1, n):
	if a[i] == curr:
		tmp += 1
		que.append((a[i], tmp))
		if tmp == k:
			for j in range(k):
				que.pop()
			if que:
				tmp = que[-1][1]
				curr = que[-1][0]
			else:
				curr = -1
	else:
		tmp = 1
		curr = a[i]
		que.append((a[i], tmp))
quecop = []
for i in que:
	quecop.append(i[0])
leftrem = 0
rightrem = 0
if not que:
	print(0)
	sys.exit()
while que[0][0] == que[-1][0]:
	r = que[0][0]
	count1 = 0
	p = len(que)
	count2 = p - 1
	while count1 < p and que[count1][0] == r:
		count1 += 1
	if count1 == p:
		break
	while count2 >= 0 and que[count2][0] == r:
		count2 -= 1
	if count1 + p - 1 - count2 < k:
		break
	leftrem += count1
	rightrem += k - count1
	for i in range(count1):
		que.popleft()
	for i in range(k - count1):
		que.pop()
if que:
	t = que[0][0]
flag = 0
for i in que:
	if i[0] != t:
		flag = 1
		break
if flag:
	print(leftrem + rightrem + len(que) * m)
else:
	r = []
	for i in range(leftrem):
		if r and r[-1][0] == quecop[i]:
			r[-1][1] += 1
		else:
			r.append([quecop[i], 1])
	if r and r[-1][0] == que[0][0]:
		r[-1][0] = (r[-1][0] + len(que) * m) % k
		if r[-1][1] == 0:
			r.pop()
	elif len(que) * m % k:
		r.append([que[0][0], len(que) * m % k])
	for i in range(len(quecop) - rightrem, len(quecop)):
		if r and r[-1][0] == quecop[i]:
			r[-1][1] += 1
			if r[-1][1] == k:
				r.pop()
		else:
			r.append([quecop[i], 1])
	finans = 0
	for i in r:
		finans += i[1]
	print(finans)