아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Допрос подозреваемых

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

요약
용의자들을 적절한 순서로 심문해 누적 지루함이 임계값을 넘는 횟수를 최소로 만들고, 그 최소 횟수와 한 가지 순서를 출력한다.
난이도

보통10점 중 6점

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

문제

Когда детектив Бенуа Бланк получил конверт с деньгами и очередное анонимное письмо с предложением заняться расследованием преступления, он сразу выдвинулся на место, чтобы опросить подозреваемых.

Всего есть nn подозреваемых, ii-й из которых характеризуется скучностью a_ia\_i. Скучность дела в каждый момент времени определяется как суммарная скучность всех свидетелей, уже давших показания.

Как известно, Бенуа Бланк терпеть не может скучные расследования. Поэтому есть mm <<критических точек>>, ii-я из которых описывается числом b_ib\_i: как только скучность дела становится больше b_ib\_i, интерес детектива к делу уменьшается на фиксированную величину.

Вы заинтересованы в том, чтобы детектив взялся за дело и довел его до конца, поэтому перед вами стоит задача расположить рассказы подозреваемых в таком порядке, при котором интерес Бенуа Бланка к делу после допроса всех подозреваемых будет максимальным.

입력

В первой строке дано целое число nn --- количество подозреваемых (1⩽n⩽2⋅1051 \leqslant n \leqslant 2 \cdot 10^5). В следующей строке через пробел перечислены nn целых чисел a_ia\_i --- значения скучности подозреваемых (−109⩽a_i⩽109-10^9 \leqslant a\_i \leqslant 10^9).

В первой строке дано целое число mm --- количество критических точек (1⩽m⩽2⋅1051 \leqslant m \leqslant 2 \cdot 10^5). В следующей строке через пробел перечислены mm целых чисел b_ib\_i --- значения этих критических точек (0⩽b_i⩽1090 \leqslant b\_i \leqslant 10^9).

출력

В первой строке выведите целое число kk --- минимально возможное число критических точек, которое может быть пройдено при допросе подозреваемых.

Во второй строке выведите через пробел nn различных целых чисел от 11 до nn --- номера свидетелей в том порядке, в котором их следует допрашивать.

Если оптимальных ответов несколько, выведите любой из них.

예제2

  1. 예제 1

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

    입력
    4
    10 -10 20 -20
    5
    11 12 3 24 15
    
    예상 출력
    0
    2 4 1 3