개구리 뛰기
시간 제한2초메모리 제한1024 MB
두 사진에서 개구리의 위치 두 집합이 주어질 때, 왼쪽으로 뛰었을 수 있는 개구리 수를 모두 오름차순으로 구합니다.
문제
줄리아는 야생 자연 사진을 좋아한다. 어제 그녀는 수련과 그 위에 앉은 개구리들이 있는 아름다운 강의 사진을 두 장 찍었다.
강에는 수련이 많이 있고, 왼쪽에서 오른쪽으로 1부터 시작하는 연속된 양의 정수로 번호가 매겨져 있다. 두 사진은 정확히 같은 장소에서 찍었고, 두 사진 모두 수련 위에 앉은 개구리가 마리로 같다. 각 수련에는 최대 한 마리의 개구리만 앉을 수 있다.
두 사진을 비교한 줄리아는 모든 개구리가 두 사진 사이에 움직였다는 것을 알아냈다. 두 사진 모두에서 개구리가 앉은 수련이 하나도 없었기 때문이다. 하지만 개구리가 모두 똑같이 생겨서, 첫 번째 사진의 어느 개구리가 두 번째 사진의 어느 수련으로 갔는지는 알 수 없었다.
확실한 것은 각 개구리가 서로 다른 수련으로 뛰었다는 점이다. 일부 개구리는 번호가 더 작은 수련으로 왼쪽으로 이동했고, 나머지 개구리는 번호가 더 큰 수련으로 오른쪽으로 이동했다.
줄리아는 개구리의 이동을 조사하려고 한다. 질문은 이것이다. 두 사진 사이에 왼쪽으로 이동한 개구리는 몇 마리인가? 이 질문의 답이 하나로 정해지지 않을 수 있으므로, 가능한 답을 모두 찾아야 한다.
입력
첫 번째 줄에는 개구리의 수를 나타내는 정수 이 하나 주어진다 ().
두 번째 줄에는 첫 번째 사진에서 개구리가 앉은 수련의 번호 이 오름차순으로 주어진다 ().
세 번째 줄에는 두 번째 사진에서 개구리가 앉은 수련의 번호 이 오름차순으로 주어진다 ().
주어지는 개의 정수는 모두 서로 다르다. 어떤 수련에도 두 사진에서 모두 개구리가 앉아 있지 않다.
출력
첫 번째 줄에 줄리아의 질문에 대한 가능한 답의 개수 를 출력한다.
두 번째 줄에 가능한 답 를 오름차순으로 출력한다 ().
힌트
첫 번째 예시에서 수련 과 에 도착한 개구리는 반드시 왼쪽으로 이동했고, 수련 과 에 도착한 개구리는 반드시 오른쪽으로 이동했다. 따라서 두 사진 사이에 왼쪽으로 이동한 개구리는 정확히 마리라는 것을 확실히 알 수 있다.