가족 찾기

면접 대비

시간 제한7초메모리 제한512 MB

요약
각 사진에 대해 나보다 큰 Alice가 내 왼쪽에, 나와 Alice보다 큰 Bob이 내 오른쪽에 올 수 있는지 판별한다.
난이도

보통10점 중 5점

유형
배열, 누적 합, 그리디, 구현
정답자
아직 제출이 없습니다

문제

당신은 자신과 가장 좋아하는 친척 Alice, Bob이 함께 찍힌 특정 가족 사진을 찾고 있다. 각 가족 사진에는 n명의 사람이 한 줄로 서 있다. 찾고 있는 사진에서, 당신보다 키가 큰 Alice는 사진사의 관점에서 당신의 왼쪽 어딘가에 있었다. 또한 당신과 Alice보다 키가 큰 Bob은 당신의 오른쪽 어딘가에 서 있었다.

가족 사진이 매우 많기 때문에 컴퓨터를 이용해 사진을 찾으려고 한다. 많은 사진이 심하게 흐릿해서 얼굴 인식은 효과가 없었다. 다행히 사진 속 각 사람을 감지해 그들의 (서로 다른) 키를 픽셀 단위로 나열해 주는 Batch Apex Photo Classifier가 훌륭한 결과를 내고 있다. k장의 사진에 대한 키 수열이 주어질 때, 이 중 어떤 사진이 당신이 찾는 사진일 가능성이 있는지 판별하라.

입력

  • 첫째 줄에 처리해야 하는 사진의 수 1≤k≤10001 \le k \le 1000이 주어진다.

  • 이어서 각 사진마다 두 줄이 주어진다.

    • 첫째 줄에 사진에 있는 사람 수 3≤n≤3⋅1053 \le n \le 3 \cdot 10^5를 나타내는 정수 하나가 주어진다.
    • 둘째 줄에 사진에 있는 사람의 키 1≤h1,…,hn≤1091 \le h_1, \ldots, h_n \le 10^9가 왼쪽에서 오른쪽 순서로 주어진다. 각 키는 서로 다르다.

모든 사진에 있는 사람 수의 합은 3⋅1053 \cdot 10^5 이하이다.

출력

  • 첫째 줄에 더 조사해야 하는 사진의 수 kk를 출력한다.
  • 이어서 kk개의 줄에 각각 살펴봐야 하는 사진의 번호 1≤ai≤n1 \le a_i \le n을 오름차순으로 한 줄에 하나씩 출력한다.

예제2

  1. 예제 1

    입력
    1
3
2 1 3
    예상 출력
    1
1

  2. 예제 2

    입력
    4
4
140 157 160 193
5
15 24 38 9 30
6
36 12 24 29 23 15
6
170 230 320 180 250 210
    예상 출력
    2
2
4