disorder

Time limit: 0.7s Memory limit: 256MB Input: Output:

Due to the restrictions caused by the Covid-19 pandemic, Rado is getting very bored, being isolated at home all by himself. He sees a deck of cards, which has NN cards and each one of them has one number between 11 and NN written on it. There aren't different cards that have equal numbers written on them. The deck is shuffled and it is placed in such a way so that the cards are with their front side up. Rado is wondering about the question: "How well is the deck shuffled?". After that he comes with another question: "How is the deck disorder defined?".

After some careful consideration, he comes with the following definition: „The disorder of a deck of cards is defined as the number of pairs of cards such that the card with the bigger number is placed above the card with the smaller number (it is not required that the two cards are placed sequentially in the deck)".

Now the question "How well is the deck shuffled?" becomes the question: "What is the disorder of the deck?". That is a problem, which is worth considering. However Rado doesn't stop with this. He starts to pull out random cards from the deck, one after another, and puts them aside but after each pulled card, he again asks himself the question "What is the disorder of the deck with the remaining cards?".

Task

Write program which answers all of Rado's questions.

Input

From the first line of the standard input your program reads one positive integer NN - the number of cards in the deck.

From the second line your program reads NN different positive integers, separated by one space, each with value between 11 and NN - the numbers, written on the cards in the deck, in the order from top to bottom.

From the third line your program reads N2N-2 different positive integers, separated by one space, each with value between 11 and NN - the numbers, written on the cards, which Rado pulls out sequentially from the deck.

Output

On the standard output your program has to print N1N-1 integers, separated by one space. The first one is the disorder of the deck before Rado starts pulling out cards. After that is the disorder when he has pulled out his first card, after that - the disorder when he has pulled out his second card and so on.

Constraints

  • 3N100 0003 ≤ N ≤ 100 \ 000
  • in 10% of the tests: N100N ≤ 100
  • in 30% of the tests: N5 000N ≤ 5 \ 000
  • in 45% of the tests: N15 000N ≤ 15 \ 000
  • Each test is evaluated separately.

Example

stdin

6
6 1 2 5 3 4
3 5 4 6

stdout

7 5 3 2 0

Log in or sign up to be able to send submissions!