세 설비의 시험 생산

문제

한 공장의 생산 라인에는 N개의 설비가 왼쪽부터 일렬로 놓여 있다. 설비 번호는 왼쪽부터 1번, 2번, …, N번이다. 각 설비는 시험 시간 동안 정해진 수의 부품을 생산한다. i번 설비의 생산량은 A_i개이며, 시험을 하는 동안 이 값은 바뀌지 않는다. 생산량이 0인 설비도 있으며, 생산된 부품은 모두 개수에 포함한다. 관리자는 서로 연속한 설비 세 개를 골라 짧은 시험 생산을 진행하려고 한다. 선택한 세 설비가 생산하는 부품은 같은 운반 상자에 담긴다. 시험 목적에 맞는 부품을 충분히 확보하면서 상자의 적재 한도를 지키기 위해, 세 설비의 생산량 합은 L 이상 R 이하여야 한다. 합이 L 또는 R과 정확히 같아도 시험을 진행할 수 있다. 세 설비보다 적거나 많이 고를 수 없으며, 생산 라인의 양 끝은 서로 연결되어 있지 않다. 시험을 진행할 수 있는 후보가 여러 개라면 생산량이 가장 고른 구간을 선택한다. 한 구간의 불균형은 그 구간에 속한 세 생산량 중 최댓값에서 최솟값을 뺀 값이다. 관리자는 불균형이 가장 작은 구간을 선택한다. 불균형이 같은 후보가 여러 개라면 가장 왼쪽에서 시작하는 구간을 선택한다. 이때 생산량 합이 더 작은지 또는 더 큰지는 추가 비교 기준으로 사용하지 않는다. 예를 들어 시작 번호가 i인 구간은 i번, i+1번, i+2번 설비로 이루어진다. 설비를 건너뛰어 고르거나 세 설비의 순서를 바꾸어 다른 구간으로 취급할 수 없다. 전체 생산량과 상자의 허용 범위가 주어졌을 때, 관리자가 선택할 구간의 시작 번호와 그 구간의 불균형을 구한다. 조건을 만족하는 구간이 하나도 없다면 시험 생산을 진행할 수 없다고 출력한다.

입력

첫째 줄에 정수 N, L, R이 공백으로 구분되어 주어진다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다.
3 ≤ N ≤ 100,000
0 ≤ L ≤ R ≤ 27
모든 i에 대하여 0 ≤ A_i ≤ 9다.

출력

시험 생산이 가능하면 선택한 구간의 시작 번호와 불균형을 공백으로 구분하여 한 줄에 출력한다. 가능한 구간이 없으면 -1을 출력한다.

7 10 16
1 4 5 4 9 2 3

2 1

5 0 0
0 1 0 1 0

-1

6 6 6
2 2 2 2 2 2

1 0

출처: Devin.KR 자체 제작