Meeting (Problem J, 2017 ICPC Asia Jakarta Regional Contest, 2017)
Time limit: 1 sec
Memory limit: 256MB
Author: Jonathan Irvin Gunawan

# Problem Statement

You are the boss of company X and have $N$ subordinates. Today, the $i$-th subordinate will come to the office $A_i$ seconds later than you.

You will have a team meeting today. Due to the capacity of the meeting room, there must be exactly $K$ people (excluding you) attending the team meeting. You can start the meeting $S$ seconds after you come to the office. You can choose the value of $S$ whatever you like, but it must be a positive real non-integer number. Everyone who is already present at the office at that start time will attend the meeting.

You can adjust the arrival time of your subordinates. By paying \$1 (one dollar) and choosing a subordinate, you can change the subordinate's arrival time by one second earlier or one second later. However, a subordinate must not arrive at the office strictly before you—that would be shameful for you. Also, a subordinate must not arrive strictly later than $T$ seconds after you—the subordinate could get fired. You can adjust the arrival time of as many subordinates as you want. You can also adjust the arrival time of the same subordinate more than once.

Determine the minimum amount of dollars needed such that you can have a meeting of exactly $K$ people (excluding you). If it is impossible to do so, output $-1$.

# Input

The first line contains three integers: $N\ K\ T$ ($1 \le K \le N \le 100,\!000$; $0 \le T \le 1,\!000,\!000,\!000$) in a line denoting the number of subordinates, the number of subordinates attending the meeting, and the maximum arrival time. The second line contains $N$ integers: $A_1\ A_2\ \cdots\ A_N$ ($0 \le A_i \le T$) in a line denoting the arrival time of each subordinate.

# Output

The output contains the minimum amount of dollars needed such that you can have a meeting of exactly $K$ people (excluding you), in a line. If it is impossible to do so, the output contains $-1$ instead.

# Sample Input
```
4 2 4
1 2 3 4
```
# Output for Sample Input
```
0
```
# Sample Input
```
4 2 4
1 2 2 4
```
# Output for Sample Input
```
1
```
# Sample Input
```
2 1 1
0 0
```
# Output for Sample Input
```
1
```
# Sample Input
```
2 1 0
0 0
```
# Output for Sample Input
```
-1
```
Explanation for the 1st sample case

For the first sample, if you start the meeting 2.5 seconds after you arrived, the meeting will be attended by the first two subordinates.

Explanation for the 2nd sample case

For the second sample, you can adjust the arrival time of the third subordinate to become one second later.

Explanation for the 3rd sample case

For the third sample, you can adjust the arrival time of the second subordinate to become one second later and start the meeting 0.71863781 seconds after you arrived.

Explanation for the 4th sample case

For the fourth sample, you cannot adjust any of the arrival time to satisfy your needs.


Sample inputs:
4 2 4
1 2 3 4

4 2 4
1 2 2 4

2 1 1
0 0

2 1 0
0 0

Sample outputs:
0

1

1

-1

# Solution Analysis
Analysis author: Jonathan Irvin Gunawan

Note that this problem can be simplified as follows:

Given an array $A$ where each element is between $0$ to $T$. In one operation, we can increment or decrement the element in the array, but must still be between $0$ to $T$. Determine the minimum number of operations such that the $K$-th smallest element is different from the $(K+1)$-th smallest element in the array.

Let $f(A)$ be the largest possible integer and $g(A)$ be the smallest possible integer such that:

- $f(A) \le K$ and the $f(A)$-th smallest element is different from the $(f(A)+1)$-th smallest element in the array.
- $g(A) \ge K$ and the $g(A)$-th smallest element is different from the $(g(A)+1)$-th smallest element in the array.

If $f(A) = g(A) = K$, then we are happy. Otherwise, we want to change $A$ into another array $A'$ with the minimum cost such that $f(A') = g(A') = K$. There are two possible ways to achieve this:

- Decrement each element from the $(f(A)+1)$-th smallest element to the $K$-th smallest element by one, if the element is still greater than $0$.
- Increment each element from the $K$-th smallest element to the $g(A)$-th smallest element by one, if the element is still less than $T$.

Among the possible ways, we use the one with fewer number of operations. If neither of the ways is possible, then we print $-1$.

Special judge (C++ scorer):