만드는 중입니다

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

개구리 뛰기

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

요약
두 사진에서 개구리의 위치 두 집합이 주어질 때, 왼쪽으로 뛰었을 수 있는 개구리 수를 모두 오름차순으로 구합니다.
난이도

보통10점 중 7점

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

문제

줄리아는 야생 자연 사진을 좋아한다. 어제 그녀는 수련과 그 위에 앉은 개구리들이 있는 아름다운 강의 사진을 두 장 찍었다.

강에는 수련이 많이 있고, 왼쪽에서 오른쪽으로 1부터 시작하는 연속된 양의 정수로 번호가 매겨져 있다. 두 사진은 정확히 같은 장소에서 찍었고, 두 사진 모두 수련 위에 앉은 개구리가 nn마리로 같다. 각 수련에는 최대 한 마리의 개구리만 앉을 수 있다.

두 사진을 비교한 줄리아는 모든 개구리가 두 사진 사이에 움직였다는 것을 알아냈다. 두 사진 모두에서 개구리가 앉은 수련이 하나도 없었기 때문이다. 하지만 개구리가 모두 똑같이 생겨서, 첫 번째 사진의 어느 개구리가 두 번째 사진의 어느 수련으로 갔는지는 알 수 없었다.

확실한 것은 각 개구리가 서로 다른 수련으로 뛰었다는 점이다. 일부 개구리는 번호가 더 작은 수련으로 왼쪽으로 이동했고, 나머지 개구리는 번호가 더 큰 수련으로 오른쪽으로 이동했다.

줄리아는 개구리의 이동을 조사하려고 한다. 질문은 이것이다. 두 사진 사이에 왼쪽으로 이동한 개구리는 몇 마리인가? 이 질문의 답이 하나로 정해지지 않을 수 있으므로, 가능한 답을 모두 찾아야 한다.

입력

첫 번째 줄에는 개구리의 수를 나타내는 정수 nn이 하나 주어진다 (1≤n≤200 0001 \le n \le 200\,000).

두 번째 줄에는 첫 번째 사진에서 개구리가 앉은 수련의 번호 a1,a2,…,ana_1, a_2, \ldots, a_n이 오름차순으로 주어진다 (1≤a1<a2<⋯<an≤1091 \le a_1 < a_2 < \cdots < a_n \le 10^9).

세 번째 줄에는 두 번째 사진에서 개구리가 앉은 수련의 번호 b1,b2,…,bnb_1, b_2, \ldots, b_n이 오름차순으로 주어진다 (1≤b1<b2<⋯<bn≤1091 \le b_1 < b_2 < \cdots < b_n \le 10^9).

주어지는 2n2n개의 정수는 모두 서로 다르다. 어떤 수련에도 두 사진에서 모두 개구리가 앉아 있지 않다.

출력

첫 번째 줄에 줄리아의 질문에 대한 가능한 답의 개수 kk를 출력한다.

두 번째 줄에 가능한 답 c1,c2,…,ckc_1, c_2, \ldots, c_k를 오름차순으로 출력한다 (0≤c1<c2<⋯<ck≤n0 \le c_1 < c_2 < \cdots < c_k \le n).

힌트

첫 번째 예시에서 수련 11과 22에 도착한 개구리는 반드시 왼쪽으로 이동했고, 수련 5151과 5252에 도착한 개구리는 반드시 오른쪽으로 이동했다. 따라서 두 사진 사이에 왼쪽으로 이동한 개구리는 정확히 22마리라는 것을 확실히 알 수 있다.

예제3

  1. 예제 1

    입력
    4
    10 20 30 40
    1 2 51 52
    
    예상 출력
    1
    2
    
  2. 예제 2

    입력
    4
    10 20 30 40
    5 15 25 35
    
    예상 출력
    4
    1 2 3 4
    
  3. 예제 3

    입력
    1
    100
    200
    
    예상 출력
    1
    0