문제
1, 2, 3, ..., 2*N-1 의 임의의 순열을 A라고 하자.
크기가 N인 배열 B는 A의 접두 중간값을 저장한 배열이다:
B[i] 에는 A[1], A[2], ..., A[2*i-1]의 중간값이 저장된다.
주의 : 중간 값은 M 개의 숫자(M은 홀수)를 정렬 했을 때, 가운데에 위치한 정수를 뜻한다.
N과 B가 주어졌을 때 원래의 순열 A를 복원하는 프로그램을 작성하라.
입력
입력은 2개의 줄로 이뤄지며, 맨 처음 줄에는 100,000 이하의 정수 N이 입력된다.
그 다음 줄에는 N개의 정수가 입력되는데, 이는 B[1], B[2], ..., B[N]을 뜻한다.
출력
입력에 대해 복원된 수열 A를 출력한다. 만약 답이 여럿이 있을 경우 이 중에서 하나를 출력한다.
입력은 답이 존재하는 경우만 들어온다고 가정한다.
예제
5
1 3 3 4 5
1 9 3 2 4 8 7 5 6
로그인해야 코드를 작성할 수 있어요.