Work, Sleep, Repeat
Description
Very talented programmers work at the VK company. Since they constantly have to solve interesting problems, work goes by quickly and with pleasure. However, this does not mean that one can completely forgo rest and sleep from it.
Programmer Lev who (almost) holds the position of a team lead decided to take a vacation. But since his presence at the workplace and availability can be critical for the team he will split this vacation into several parts: namely, he will live in a cyclical mode of "work for $x$ days, then take a vacation for $y$ days" for the foreseeable future.
Of course, he has planned meetings with the team, release days for new versions, and other events that cannot be missed. There are a total of $n$ such events and the $i$-th of them is scheduled for day $d_i$.
Assuming that today is day number $1$, and all events are scheduled for no earlier than day number $1$, determine if there exists a day $D \le x + y$ such that if Lev switches to the new mode on day $D - x - y$, he will not miss any scheduled events. In other words, it is required to ensure that all days $d_i$ fall on the work phase in the corresponding cycle.
The first line of input contains three space-separated integers $n$, $x$ and $y$ — the number of scheduled events, as well as the length of the work phase and the length of the vacation phase planned by Lev ($1 \le n \le 2 \cdot 10^5$; $1 \le x, y \le 10^9$).
The second line lists $n$ space-separated integers $d_i$ — the days on which events are scheduled ($1 \le d_i \le 10^9$). It is not guaranteed that all $d_i$ are different.
Output a single integer between $1$ and $x + y$ — the day number on which Lev should switch to the new mode. If there are several possible answers, output any of them. If there is no answer, output -1.
Scoring
Points for each subtask are awarded only if all tests of that subtask and the required subtasks are successfully passed.
| Subtask | Points | Constraints | Required subtasks |
| 0 | – | examples | |
| 1 | 15 | $x = 1$ | |
| 2 | 19 | $n, x, y \le 1000$ | 0 |
| 3 | 18 | $y = 1$ | |
| 4 | 21 | $x \le y$ | 0, 2 |
| 5 | 27 | none | 0 – 4 |
Input
The first line of input contains three space-separated integers $n$, $x$ and $y$ — the number of scheduled events, as well as the length of the work phase and the length of the vacation phase planned by Lev ($1 \le n \le 2 \cdot 10^5$; $1 \le x, y \le 10^9$).
The second line lists $n$ space-separated integers $d_i$ — the days on which events are scheduled ($1 \le d_i \le 10^9$). It is not guaranteed that all $d_i$ are different.
Output
Output a single integer between $1$ and $x + y$ — the day number on which Lev should switch to the new mode. If there are several possible answers, output any of them. If there is no answer, output -1.
3 3 1
5 8 11
4 3 1
5 8 11 14
5 4 3
10 16 17 18 99
3
-1
1
Note
In the first example if the second cycle starts on the third day Lev will work on days 3–5, then 7, 8, 9, and finally, 11–13.