题目描述

The organizers of the Closed Olympiad in Informatics decided to prepare gifts for the participants of the Olympiad. A total of $k$ same gift boxes were prepared, each box contains a stack of $n$ gifts. At the top of each stack there is a gift of type $a_1$, below it there is a gift of type $a_2$, and so on, at the bottom of the stack there is a gift of type $a_n$.

The distribution of gifts will be as follows: at the beginning, gifts from the first stack will be given out from top to bottom. After there are no more gifts left in the first stack, gifts from the second stack will be given from top to bottom, and so on, in the end gifts from the $k$-th stack will be given.

A participant can receive several gifts at once, so at the beginning gifts will be given to the first participant, then to the second, and so on. It is known that if a participant receives more than $t$ different types of gifts, the participant will be too happy and will write the Olympiad poorly. In order for the participants to write the Olympiad well, it was decided to give each participant no more than $t$ different types of gifts (note that a participant may receive several gifts of the same type).

The organizers of the Closed Olympiad in Informatics decided to make the Olympiad exclusive and invite as few participants as possible. Help the organizers find out the minimum number of participants they can invite so that all the gifts are distributed to the participants, and each participant receives no more than $t$ different types of gifts.

输入格式

The first line of the input contains three integers $n$, $k$, and $t$ ($1 \le n \le 300\,000$, $1 \le k, t \le 10^9$) --- the number of gifts in one stack, the number of stacks of gifts, and the maximum number of different types of gifts that can be received by one participant.

The second line contains $n$ integers $a_1,\ a_2,\ \ldots,\ a_n$ ($1 \le a_i \le 10^9$) --- the types of gifts, in the order from top to bottom of the stack.

输出格式

Output a single number --- the minimum number of participants, such that all the gifts will be distributed to them, and each participant receives no more than $t$ different types of gifts.

2 4 1
1 2

8

4 3 1
1 1 2 1

7

7 2 3
1 2 3 4 5 6 7

5

提示

Note

In the first example, the stack contains the following types of gifts (in order from top to bottom). Different colors denote different positions in the stack.

:::align{center} :::

There are a total of 4 stacks of gifts, so the gifts will be given out in the following order:

:::aligned{center} :::

Since $t = 1$, each participant in this case can only receive gifts of one type:

:::aligned{center} :::

In the second example, the order of gift distribution and the final sets of gifts are following:

:::aligned{center} :::

In the third example, the order of gift distribution is as follows:

:::aligned{center} :::

In this case, one of the possible optimal distribution of gifts into sets is the following:

:::aligned{center} :::

Scoring

The tests for this problem consist of six groups. Points for each group are given only if all tests of the group and all tests of the required groups are passed. Note that passing the example tests is not required for some groups.

Group	Points	Additional constraints	<		Required groups	Comment
		$n$	$k$	$t$
0		--		--	--	Examples.
1	14	$n \le 100$	$k \le 10$		0	--
2	12	--		$t = 1$	--
3	16	$n \le 1000$	$k \le 1000$	--	0, 1
4	21	$n \le 1500$	$k \le 10^6$		0, 1, 3
5	18	--			0, 1, 3, 4
6	19		--		0 -- 5