Лесопилка

시간 제한2초메모리 제한1024 MB

요약
톱의 좌표들이 주어질 때, 길이 l인 통나무를 잘라 생기는 모든 토막의 길이가 [a, b]에 들어가도록 왼쪽 끝 좌표를 정한다.
난이도

어려움10점 중 8점

유형
배열, 이분 탐색, 수학, 누적 합
정답자
아직 제출이 없습니다

문제

После того, как дуб, в котором жила Сова, упал, ей понадобилось новое жилище. Так как больше деревьев с большими удобными дуплами не осталось, Сова решила распилить несколько старых засохших деревьев на бревна.

Так как пилить Сове совсем не хочется, она обратилась на ближайшую лесопилку. Эта лесопилка, как и многие другие, использует инновационные технологии --- на ней установлен автоматический разрезатель бревен. Он состоит из очень длинной линейки, вдоль которой отсчитываются координаты, фиксатора ствола дерева и nn неподвижных лазерных пил. Левый конец разрезаемого ствола закрепляется фиксатором в некоторой точке, и ствол разрезается во всех местах, координаты которых совпадают с координатами пил.

Так как Сове для постройки дома подходят только бревна, длина которых не меньше aa и не больше bb, то для каждого из стволов деревьев, которые у нее есть, Сова хочет узнать, можно ли его распилить на лесопилке на такие бревна.

입력

В первой строке входного файла записано одно целое число nn (1≤n≤106)(1 \le n \le 10^6) --- количество пил на лесопилке. В следующей строке записано nn целых чисел x_ix\_i (∣x_i∣≤109)(|x\_i| \le 10^9) --- координаты ii пилы. Координаты всех пил различны.

В следующей строке записано три целых числа: ll (1≤l≤109)(1 \le l \le 10^9) --- длина ствола, который хочет распилить Сова, aa и bb (1≤a≤b≤109)(1 \le a \le b \le 10^9) --- длины самого короткого и самого длинного бревна, которые подходят Сове.

출력

В выходной файл выведите одно целое число --- координаты точки, в которой нужно установить левый конец бревна, чтобы оно распилилось на подходящие Сове бревна. Если такой точки не существует, выведите <<No solution>>.

예제2

  1. 예제 1

    입력
    3
    0 1 3
    3 1 1
    
    예상 출력
    -1
    
  2. 예제 2

    입력
    3
    0 1 3
    4 1 1
    
    예상 출력
    No solution