Jumping Frogs

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

요약
서로 겹치지 않는 두 집합 A와 B가 주어질 때, 왼쪽으로 이동한 개구리 수로 가능한 값을 모두 구한다.
난이도

보통10점 중 7점

유형
그리디, 정렬, 투 포인터, 조합론
정답자
아직 제출이 없습니다

문제

Julia is a fan of wild nature photos. Yesterday, she took two photos of a beautiful river with water lilies and some frogs sitting on them.

There are many water lilies on the river, numbered with consecutive positive integers from left to right, starting from 11. Both photos were taken from exactly the same spot, and both photos have the same nn frogs sitting on water lilies. Each water lily can hold at most one frog.

After comparing the photos, Julia found out that all the frogs moved between the photos, since no water lily had a frog sitting on it in both photos. However, Julia couldn't understand which frog from the first photo moved to which water lily in the second photo, as all frogs looked exactly the same!

One thing is for sure: each frog jumped to a different water lily. Some frogs moved to the left, to a water lily with a smaller number, while the other frogs moved to the right, to a water lily with a larger number.

To investigate the movement of frogs, Julia wants to answer the following question: how many frogs moved to the left between the photos? As it may not be possible to find a unique answer to this question, you need to help Julia to find all possible answers.

입력

The first line contains a single integer nn, denoting the number of frogs (1≤n≤200,0001 \le n \le 200\\,000).

The second line contains nn integers a_1,a_2,…,a_na\_1, a\_2, \ldots, a\_n, denoting the water lilies with frogs on them in the first photo, in increasing order (1≤a_1<a_2<⋯<a_n≤1091 \le a\_1 < a\_2 < \cdots < a\_n \le 10^9).

The third line contains nn integers b_1,b_2,…,b_nb\_1, b\_2, \ldots, b\_n, denoting the water lilies with frogs on them in the second photo, in increasing order (1≤b_1<b_2<⋯<b_n≤1091 \le b\_1 < b\_2 < \cdots < b\_n \le 10^9).

All 2n2n given integers are distinct: no water lily has a frog sitting on it in both photos.

출력

In the first line, print a single integer kk, denoting the number of possible answers to Julia's question.

In the second line, print kk integers c_1,c_2,…,c_kc\_1, c\_2, \ldots, c\_k, denoting all possible answers in increasing order (0≤c_1<c_2<⋯<c_k≤n0 \le c\_1 < c\_2 < \cdots < c\_k \le n).

힌트

In the first example, frogs that ended up on water lilies 11 and 22 must have moved to the left, while frogs that ended up on water lilies 5151 and 5252 must have moved to the right. Thus, we know for sure that exactly 22 frogs moved to the left between the photos.

예제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