시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 256 MB 56 19 9 28.125%

문제

직선 형태의 강에 N+1개의 댐이 있다. 가장 왼쪽 댐의 왼쪽과 가장 오른쪽 댐의 오른쪽으로는 강이 더 이상 이어지지 않기에, 댐으로 인해 강은 길이가 같은 N개의 구간으로 나뉘어져 있다. 각 구간에서 강의 수위는 서로 다를 수 있다.

지나친 수질오염으로 인해 당신은 N+1개의 댐 중 몇 개를 파괴하기로 결정했다. 적어도 한 개의 댐을 파괴하여야 하며, 당연하지만 양쪽 끝에 있는 댐은 파괴할 수 없다.

댐을 파괴하고 나면 댐 양옆에 있던 물의 수위가 같아지도록 물이 이동할 것이다. 예를 들어 N=5이고 최초에 강의 수위가 다음과 같은 수열로 표현되었다고 하자.

2 5 2 6 9

이 상태에서 두 번째, 세 번째, 다섯 번째 댐을 파괴한다면 강의 수위는 다음과 같게 변한다.

3 3 3 7.5 7.5

그러나 몇몇 댐을 파괴함으로 인해 강의 수위가 급격하게 바뀐다면 다른 댐들도 균형을 잃고 무너질 수 있다.

N+1개의 댐에 대해 댐이 견딜 수 있는 강의 수위의 범위가 주어진다. 만약 어떤 댐의 왼쪽 혹은 오른쪽에 오는 강의 구간의 수위가 그 댐이 견딜 수 있는 수위의 범위를 벗아난다면 그 댐은 무너질 것이다. 초기 상태에서는 모든 댐이 무너지지 않는 상태임이 보장된다.

양쪽 끝에 있는 댐을 제외한 적어도 한 개의 댐을 파괴하고 나서, 다른 댐은 무너지지 않게 하는 방법을 제시하여라.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 300,000)

두 번째 줄에는 댐으로 인해 나뉘어진 N개의 구간에서 강의 수위를 나타내는 수열 A가 주어진다. (1 ≤ Ai ≤ 7,777,777)

그 뒤로 N+1개의 줄에는 각 댐의 정보가 주어진다. i번째 댐의 정보는 두 정수 li과 ui로 표현되며 이는 그 댐이 견딜 수 있는 강의 수위가 li이상 ui이하임을 뜻한다. (1 ≤ li ≤ ui ≤ 7,777,777)

자연수 i (1 ≤ i ≤ N)에 대해 l≤ h≤ ui 이며 li+1 ≤ h≤ ui+1 이다.

출력

첫째 줄에 파괴할 댐의 수 K를 출력한다. (1 ≤ K ≤ N - 1)

둘째 줄에 파괴할 댐의 번호 K개를 공백으로 구분하여 출력한다. 댐의 인덱스는 0부터 시작한다. 따라서 당신이 출력해야 할 댐의 번호는 1 이상 N-1 이하이다. 댐의 번호는 모두 서로 달라야 한다.

만약 조건을 만족하도록 댐을 파괴하는 방법이 존재하지 않는다면 첫째 줄에 -1을 출력하여라.

예제 입력 1

5
2 5 2 6 9
2 4
2 5
2 5
2 8
6 9
6 9

예제 출력 1

3
1 2 4

예제 입력 2

5
4 5 9 4 5
4 4
4 6
4 10
4 10
4 5
5 5

예제 출력 2

-1

출처

High School > 서울과학고등학교 > 2020 SciOI #1 D번