만드는 중입니다

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

의심스러운 보고서 (Basic)

면접 대비

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

요약
전체 보고서 s에서 t와 같은 모양의 위쪽 단면을 이루는 열 번호를 찾을 수 있는지 판별합니다.
난이도

쉬움10점 중 3점

유형
완전 탐색, 구현, 배열
정답자
아직 제출이 없습니다

문제

에디 브록은 결국 기자다. 베놈을 만나기 전 그는 생명 재단의 온갖 악행을 폭로하는 신랄한 기사를 쓰고 있었다. (네, 다시 첫 번째 영화 시절로 돌아갑니다. 어쩔 수 없네요.) 지금 그는 최근 발견된 재단의 재무 보고서를 살펴보며 불법 활동의 흔적(예를 들어 사람을 대상으로 한 실험)을 추적하고 있다.

각 보고서는 길이 mm의 배열 sis_i이며, 높이가 다른 기둥들로 이루어진 히스토그램으로 표현된다. 회계담당자는 다음 방식으로 어떤 기록이 불법 작업에 해당하는지 표시한다.

  1. 먼저 히스토그램에서 ll부터 rr까지의 구간을 고른다. 이 구간에는 가장 불법적인 작업 nn개의 기록이 l⩽i1<i2<…<in⩽rl \leqslant i_1 < i_2 < \ldots < i_n \leqslant r 위치의 열로 들어 있어야 한다.
  2. 그다음 ll번 열부터 rr번 열까지 높이 hh(음수일 수도 있음)에 수평선을 긋는다. 가장 비용이 많이 드는 불법 작업의 열은 모두 선보다 엄격히 위에 있고, 합법 작업의 열은 선보다 위에 있지 않아야 한다. 형식적으로는 i∈i1,…,ini \in i_1, \ldots, i_n인 것이 si>hs_i > h인 것과 같아야 한다.
  3. 그 후 불법 작업 보고서를 길이 nn의 수열 tj=sij−ht_j = s_{i_j} - h로 비밀 폴더에 저장한다. 쉽게 말해 원래 히스토그램을 높이 hh에서 자른 윗부분이다.

에디는 신뢰할 수 있는 전체 보고서와, 익명의 제보자가 보낸 불법 작업 보고서를 가지고 있다. 제보자는 이 불법 작업 보고서가 위에서 설명한 방식으로 전체 보고서에서 나왔다고 주장한다. 에디는 전체 보고서의 어느 열이 불법 작업에 해당하는지만 알고 싶어 한다.

몇 가지 예를 보자. 먼저 재단의 전체 보고서이고, 그다음은 불법 작업의 히스토그램이다.

두 번째 예를 제외한 모든 예에서는 같은 수평선을 기준으로 지정된 높이 sjs_j에 놓인 열들의 부분수열을 고를 수 있다(나머지 열은 선 아래에 있다). 두 번째 예에서는 선 위에 여분의 열이 하나 있어서 이것이 불가능하다. l=1l = 1, r=nr = n일 필요는 없다는 점에 유의하라.

입력

첫 줄에 불법 작업 보고서의 길이 nn이 주어진다 (1⩽n⩽5001 \leqslant n \leqslant 500).

둘째 줄에는 재단의 모든 불법 작업 열 높이 tit_i가 공백으로 구분되어 nn개 주어진다 (1⩽ti⩽1061 \leqslant t_i \leqslant 10^6).

셋째 줄에 재단의 전체 보고서 길이 mm이 주어진다 (n⩽m⩽500n \leqslant m \leqslant 500).

다음 줄에는 전체 보고서의 기록 sis_i가 공백으로 구분되어 mm개 주어진다.

출력

보고서가 설명한 방식으로 전체 보고서에서 만들어질 수 있었다면 첫 줄에 YES를, 그렇지 않으면 NO를 출력한다.

YES를 출력했다면 둘째 줄에 재단의 불법 작업에 해당하는 전체 보고서의 열 번호 i1,i2,…,ini_1, i_2, \ldots, i_n을 공백으로 구분해 출력한다 (1⩽i1<i2<…<in⩽m1 \leqslant i_1 < i_2 < \ldots < i_n \leqslant m).

예제4

  1. 예제 1

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

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

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

    입력
    3
    5 5 5
    5
    5 3 3 3 5
    
    예상 출력
    YES
    2 3 4