카드 섞기

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

요약

초기 상태에서 (2, K) 섞기를 두 번 한 뒤의 카드 더미가 주어질 때, 각 섞기에 쓰인 K 값을 구합니다.

문제

마술사 영재는 카드 더미를 이용한 마술을 개발하였다.

카드에는 1부터 $N$ 까지의 숫자가 적혀 있다. 초기 상태에서는 1이 맨 위에 있고, $N$ 개의 카드가 번호 순서대로 쌓여 있다.

영재는 마술을 위해 $(2, K)$ -섞기를 만들었다. $(2, K)$ -섞기는 총 $K+1$ 개의 단계로 이루어진다.

첫 번째 단계에서는 카드 더미의 맨 아래에서 $2K$ 개의 카드를 더미의 맨 위로 올린다. $i$ 번째 단계( $2 \le i \le K+1$ )에서는 직전 단계에서 맨 위로 올린 카드 중 맨 아래에서 $2K-i+1$ 개의 카드를 더미의 맨 위로 올린다.

예를 들어 카드가 5개일 때, 초기 상태에서 $(2, 2)$ -섞기를 하는 과정은 다음과 같다. (괄호 안에서 왼쪽에 있을수록 위에 있는 카드이다.)

영재의 마술은 초기 상태에서 $(2, K)$ -섞기를 2번 한 결과를 보고, 2번의 $(2, K)$ -섞기에서 $K$ 가 각각 무엇인지 맞추는 것이다.

영재는 마술 아이디어는 떠올렸지만 $K$ 를 알아내는 방법을 모른다. $K$ 를 알아내는 프로그램을 작성하라.

2번의 $(2, K)$ -섞기 후의 카드 더미 결과를 만드는 각각의 $K$ 는 유일함이 보장된다.

첫 줄에 $N$ 이 주어진다.

둘째 줄에 2번의 $(2, K)$ -섞기 후의 카드 더미가 위에 있는 카드부터 공백으로 구분하여 주어진다.

첫 번째 $K$ 와 두 번째 $K$ 를 출력한다.