카드 덱의 어지러움
시간 제한0.7초메모리 제한1024 MB
1부터 N까지의 순열과 순서대로 뽑히는 N-2장의 카드가 주어질 때, 처음 상태와 카드를 한 장씩 뽑은 뒤 남은 덱의 반전 수를 차례로 출력한다.
문제
Covid-19 팬데믹으로 인한 제한 조치 때문에 Rado는 혼자 집에 격리되어 매우 지루해하고 있다. 그는 카드 덱 하나를 발견하는데, 이 덱에는 N장의 카드가 있고 각 카드에는 1부터 N 사이의 수 하나가 적혀 있다. 같은 수가 적힌 서로 다른 카드는 없다. 덱은 섞여서 앞면이 위로 오도록 놓여 있다. Rado는 "이 덱은 얼마나 잘 섞였을까?"라는 질문을 떠올린다. 그다음에는 "덱의 어지러움은 어떻게 정의할까?"라는 질문을 떠올린다.
곰곰이 생각한 끝에 그는 다음과 같이 정의한다. "카드 덱의 어지러움은, 큰 수가 적힌 카드가 작은 수가 적힌 카드보다 위에 놓인 카드 쌍의 수로 정의한다. 두 카드가 덱에서 연속해 있을 필요는 없다."
이제 "이 덱은 얼마나 잘 섞였을까?"라는 질문은 "이 덱의 어지러움은 얼마인가?"라는 질문이 된다. 이는 생각해 볼 가치가 있는 문제이다. 그러나 Rado는 여기서 멈추지 않는다. 그는 덱에서 카드를 하나씩 무작위로 뽑아 옆에 놓기 시작하는데, 카드를 뽑을 때마다 다시 "남은 카드로 이루어진 덱의 어지러움은 얼마인가?"라는 질문을 떠올린다.
Rado의 모든 질문에 답하는 프로그램 disorder를 작성하라.
입력
표준 입력의 첫째 줄에서 프로그램은 양의 정수 N을 읽는다. N은 덱에 있는 카드의 수이다.
둘째 줄에서 프로그램은 공백 하나로 구분된 N개의 서로 다른 양의 정수를 읽는다. 각 값은 1과 N 사이이며, 덱에 있는 카드에 적힌 수를 위에서 아래 순서대로 나타낸다.
셋째 줄에서 프로그램은 공백 하나로 구분된 N-2개의 서로 다른 양의 정수를 읽는다. 각 값은 1과 N 사이이며, Rado가 덱에서 순서대로 뽑는 카드에 적힌 수이다.
출력
표준 출력에 공백 하나로 구분된 N-1개의 정수를 출력한다. 첫 번째는 Rado가 카드를 뽑기 시작하기 전 덱의 어지러움이다. 그다음은 첫 번째 카드를 뽑은 뒤의 어지러움, 그다음은 두 번째 카드를 뽑은 뒤의 어지러움, 이런 식으로 이어진다.