미니 마켓

인도네시아에 있는 두 대형 미니 마켓 회사는 Amart(ACMmart)와 Imart(ICPCmart)다. 인도네시아에는 왼쪽에서 오른쪽으로 일렬로 늘어선 $N$개의 지점이 있다. 가장 왼쪽 지점의 번호는 1이고 가장 오른쪽 지점의 번호는 $N$이다. 각 지점에는 사람이 정확히 한 명씩 있다. 지점 $i$에서 지점 $j$까지의 거리는 $|i - j|$다. 인도네시아에는 정확히 $M$개의 Amart와 $K$개의 Imart가 있다. 모든 사람은 가장 가까운 미니 마켓으로 간다. 가장 가까운 Amart와 가장 가까운 Imart까지의 거리가 같으면 Imart로 간다. 그날 Amart를 찾아간 사람의 총수가 Amart의 방문자 수다. 마찬가지로 그날 Imart를 찾아간 사람의 총수가 Imart의 방문자 수다. $i$번째 Amart는 지점 $A_i$에 있다. Imart의 방문자 수가 최대가 되도록 $K$개의 Imart 위치를 정하려 한다. 한 지점에 미니 마켓을 둘 이상 놓을 수도 있다.

첫째 줄에 세 정수 $N$, $M$, $K$가 주어진다($1 \le K \le N \le 2{,}000{,}000{,}000$, $1 \le M \le 100{,}000$). 각각 지점의 수, Amart의 수, Imart의 수다. 둘째 줄에는 Amart의 위치 $A_1, A_2, \ldots, A_M$($1 \le A_i \le N$)이 주어진다.

Imart 방문자 수의 최댓값을 한 줄에 출력한다.