만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

공격 쌍

면접 대비

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

요약
n개의 값에서 인덱스 차이가 k 이하이고 값의 차이가 l 이상 r 이하인 쌍을 하나 찾고, 없으면 -1 -1을 출력합니다.
난이도

보통10점 중 6점

유형
슬라이딩 윈도우, 이분 탐색, 정렬
정답자
아직 제출이 없습니다

문제

수중 세계에 어려운 시기가 찾아왔고 전쟁이 벌어졌다. 아쿠아맨은 서로 다른 생물 nn마리로 군대를 꾸려 일렬로 세우고 1번부터 nn번까지 번호를 붙였다. ii번 생물의 힘은 aia_i이다.

아쿠아맨은 어머니에게서 다음 전투 기술을 배웠다. 생물 두 마리를 한 쌍으로 전투에 보내 적군에 정확한 일격을 가한 뒤, 곧바로 원래 자리로 돌아오게 하는 것이다. 다만 아무 쌍이나 보낼 수 있는 것은 아니다. 다음 조건을 만족하는 1≤i,j≤n1 \le i, j \le n인 쌍만 보낼 수 있다.

{1≤∣i−j∣≤kl≤∣ai−aj∣≤r\begin{cases} 1 \le |i - j| \le k \\ l \le |a_i - a_j| \le r \end{cases}

우선 군대에 승산이 있는지 알아보기 위해, 전투에 보낼 수 있는 쌍을 하나 찾고자 한다. 그의 일을 도와라.

입력

첫째 줄에 네 정수 nn, kk, ll, rr이 주어진다. 각각 아쿠아맨 군대의 생물 수, ∣i−j∣|i - j|에 대한 제한, ∣ai−aj∣|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).

둘째 줄에 생물들의 힘 a1,a2,…,ana_1, a_2, \ldots, a_n이 nn개의 정수로 주어진다 (1≤ai≤1091 \le a_i \le 10^9).

출력

전투에 보낼 수 있는 쌍이 존재하면, 두 생물의 번호 ii와 jj를 한 줄에 출력한다. 가능한 쌍이 여러 개라면 그중 아무거나 출력해도 된다. 그런 쌍이 없으면 −1-1과 −1-1을 한 줄에 출력한다.

힌트

첫 번째 예제에서 아쿠아맨이 전투에 보낼 수 있는 쌍은 하나뿐이며, a3=6a_3 = 6과 a5=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