Alice and Bob are hanging out in a park near the university!
Unfortunately, since classes are happening, people keep walking through the park, disturbing the pair! There are classes, and the -th class ends at minute , at which point students walk through the park. Thankfully, they only take minute to leave the clearing.
Alice and Bob will stay in the park for minutes, from minute to minute . Bob hates being disturbed, and so by bribing the university, he can make at most one class up to minutes earlier or later (which will of course change when those students enter the park).
If he changes the time of at most one class optimally, what is the maximum contiguous section of time he and Alice can spend undisturbed?
is sorted in strictly increasing order.
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [70%]
No additional constraints.
The first line will contain three integers, , and .
The next line will contain integers, the array .
Output the maximum time Bob and Alice can spend undisturbed if Bob moves the class optimally.
Sample Input 1
2 10 2 1 7
Sample Output 1
Explanation for Sample 1
By moving the second class back by two minutes, Alice and Bob can spend the time from minute to minute uninterrupted.
Sample Input 2
3 8 5 1 7 8
Sample Output 2
Explanation for Sample 2
One possible solution is for Bob to make the first class end at time (before Alice and Bob arrive), and then Alice and Bob will have the time from minute to minute uninterrupted.