You_need_to_train_more — OOI qualification
Task type: batch | Time limit: 1 s | Memory limit: 256 MB | Difficulty: 24
Algorithms: line sweep, sorting, modular arithmetic, interval dp

# You need to train more

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 1 second        |
| Memory limit: | 256 megabytes   |

Anton is in the 6th grade and actively preparing for programming competitions. At the moment, he has solved $n$ problems, and he solved the $i$-th problem at hour $t_i$.

There are $m$ time zones, numbered from $0$ to $m - 1$. In each time zone, one day consists of $m$ consecutive hours. In the $k$-th time zone, the $d$-th day consists of hours numbered from $d \cdot m + k$ to $(d + 1) \cdot m + k - 1$ (inclusive). Note that $d$ can be negative.

At the beginning of the year, Anton set a goal to solve at least one problem every day. Now he wants to check if there is such a time zone and two days $l$ and $r$ such that on any of these days, he solved at least one problem, and any solved problem was solved exactly on one of the days from $l$ to $r$ in this time zone.

Help Anton find such a time zone or determine that it does not exist. If there are several suitable time zones, find the minimum one.

## Input

The first line contains two integers, $n$ and $m$ ($1 \le n \le 200\,000$, $1 \le m \le 10^9$) — the number of problems solved and the number of hours in each day, respectively.

The second line contains $n$ integers $t_1, t_2, t_3, \dots, t_n$ ($0 \le t_i \le 10^9$, $t_i \le t_{i+1}$) — the submission time of each problem in non-decreasing order.

## Output

Output one integer — the minimum number of the suitable time zone, or $-1$ if it does not exist.

## Examples

| standard input        | standard output |
|-----------------------|-----------------|
| 3 3<br>4 5 10         | 2               |
| 4 5<br>2 4 14 17      | -1              |
| 6 3<br>1 2 6 10 11 12 | 2               |

## Note

In the first example, the day lasts for 3 hours, and Anton solved 3 problems: in hours 4, 5, and 10, respectively.

- In time zone 0, Anton's submissions fall on days 1, 1, and 3, respectively. Since Anton did not make any submissions on day 2, this time zone is not suitable.
- In time zone 1, Anton's submissions fall on days 1, 1, and 3, respectively. Since Anton did not make any submissions on day 2, this time zone is not suitable.
- In time zone 2, Anton's submissions fall on days 0, 1, and 2, respectively. The days form a continuous interval, so this time zone is suitable. Since it is the minimum among the suitable ones, 2 is the answer to the problem.

In the second example, none of the time zones is suitable.

In the third example:

- In time zone 0, Anton's submissions fall on days 0, 0, 2, 3, 3, and 4, respectively. Since Anton did not make any submissions on day 1, this time zone is not suitable.
- In time zone 1, Anton's submissions fall on days 0, 0, 1, 3, 3, and 3, respectively. Since Anton did not make any submissions on day 2, this time zone is not suitable.
- In time zone 2, Anton's submissions fall on days -1, 0, 1, 2, 3, and 3, respectively. The days form a continuous interval from -1 to 3, so this time zone is the answer.

## Scoring

The tests for this problem consist of 5 groups. Points for each group are awarded only if all the tests in that group and some tests from the previous groups pass.

| Group | Score | Additional constraints |   |   | Required groups | Comment  |
|-------|-------|-----------------------|---|---|-----------------|----------|
|       |       | $n$                   | $m$ | $t_i$          |       |      |
| 0     | 0     | –                     | – | –             | –               | Samples. |
| 1     | 18    | $n \le 500$           | $m \le 100$ | –             | 0               |          |
| 2     | 19    | –                     | $m \le 100$ | –             | 0, 1            |          |
| 3     | 16    | $n \le 500$           | – | $t_i \le 500$ | 0               |          |
| 4     | 21    | $n \le 5000$          | – | $t_i \le 500$ | 0, 3            |          |
| 5     | 26    | –                     | – | –             | 0 – 4           |          |

Starter code: