아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Атакующие пары

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

요약
거리가 k 이하이면서 값의 차이가 l 이상 r 이하인 두 원소의 위치를 찾아 출력한다. 없으면 -1 -1을 출력한다.
난이도

보통10점 중 5점

유형
배열, 정렬, 슬라이딩 윈도우, 투 포인터
정답자
아직 제출이 없습니다

문제

В подводном мире настали тяжелые времена, развязалась война. Аквамен собрал свою армию из nn разных существ, расставил их в линию и пронумеровал от 11 до nn. Таким образом получилось, ii-е существо имеет силу a_ia\_i.

Еще от своей матери Аквамен узнал следующую технику ведения боя: в бой посылаются пары существ, которые наносят точечный удар по армии противника, а затем сразу же возвращаются в строй на свои места. Однако, не все так просто, не каждую пару существ можно отправить в бой: подходят только такие пары существ 1≤i,j≤n1 \le i, j \le n, что \begin{equation\*} \begin{cases} 1 \le |i - j| \le k\\\ l \le |a\_i - a\_j| \le r \end{cases} \end{equation\*}

Для начала, чтобы понять, есть ли у его армии хоть какие-то шансы на победу, Аквамен хочет найти любую пару существ, которую можно отправить в бой. Помогите ему.

입력

В первой строке содержится четыре числа nn, kk, ll, rr --- количество существ в армии Аквамена, а также ограничения на разницу ∣i−j∣|i - j| и ∣a_i−a_j∣|a\_i - a\_j| соответственно (2≤n≤1052 \le n \le 10^5, 1≤k<n1 \le k < n, 0≤l≤r≤1090 \le l \le r \le 10^9).

Во второй строке содержится nn чисел a_1a\_1, a_2a\_2, \ldots, a_na\_n --- силы существ в армии Аквамена (1≤a_i≤1091 \le a\_i \le 10^9).

출력

Если существует пара существ, которую можно отправить, в единственной строке выведите два числа ii и jj --- номера этих существ. Если существует несколько возможных пар, выведите любую. Если же такой пары не существует, в единственной строке выведите два числа --- −1-1 и −1-1.

힌트

В первом примере у Аквамена есть только одна пара существ, которую можно отправить в бой --- a_3=6a\_3 = 6 и a_5=4a\_5 = 4: 1≤∣3−5∣≤21 \le |3 - 5| \le 2 и 2≤∣6−4∣≤32 \le |6 - 4| \le 3.

Во втором примере для того, чтобы пару существ можно было отправить в бой, нужно, чтобы силы существ были равны, однако в массиве нет пары одинаковых элементов.

예제2

  1. 예제 1

    입력
    5 2 2 3
    2 1 6 5 4
    
    예상 출력
    3 5
    
  2. 예제 2

    입력
    5 2 0 0
    2 1 6 5 4
    
    예상 출력
    -1 -1