울타리 칠하기

어느 맑은 날 소븐야는 북서쪽에 있는 자기 나무 주위의 울타리를 칠하기로 했다. 예전에 한 번 칠한 적이 있었지만 페인트가 벗겨졌고, 다시 칠했다가 또 벗겨지기를 반복했다. 그래서 지금 울타리는 처음 모습을 완전히 잃었다.

울타리는 번호가 매겨진 $n$개의 널빤지로 이루어져 있고, 각 널빤지의 색은 $1$부터 $k$까지 중 하나이다. 소븐야는 먼저 칠을 마쳤을 때 모든 널빤지가 가질 색을 하나 고른다. 그다음 매일 번호가 $l$ 이상 $r$ 이하인 구간의 모든 널빤지를 그 색으로 칠한다. 소븐야는 칠하는 날 수가 가장 적도록 색을 고르려 한다.

칠할 때 지켜야 할 규칙이 두 가지 있다. 첫째, 하루에 최대 $s$개의 널빤지만 칠할 수 있다. 둘째, 이미 그 색인 널빤지는 다시 칠하지 않는다. 따라서 칠하려는 구간 안에 목표 색인 널빤지가 하나라도 있으면 그 구간은 그 색으로 칠할 수 없고, 다른 구간을 골라야 한다.

소븐야가 울타리를 칠하는 데 며칠이 걸리는지 구하라.

첫 줄에 세 정수 $n$, $k$, $s$가 주어진다 ($1 \le n, k, s \le 100\,000$). $n$은 널빤지의 개수, $k$는 가능한 색의 개수, $s$는 하루에 칠할 수 있는 최대 널빤지 수이다. 둘째 줄에는 울타리의 색 $c_i$ ($1 \le c_i \le k$)가 공백으로 구분되어 주어진다.

정수 하나를 출력한다. 소븐야가 울타리를 칠하는 데 걸리는 최소 날 수이다.