Vasya and Books
Contest: Educational Codeforces Round 53 (Rated for Div. 2)
Difficulty rating: 1000
Tags: implementation, math

Vasya has got $$$n$$$ books, numbered from $$$1$$$ to $$$n$$$, arranged in a stack. The topmost book has number $$$a_1$$$, the next one — $$$a_2$$$, and so on. The book at the bottom of the stack has number $$$a_n$$$. All numbers are distinct.

Vasya wants to move all the books to his backpack in $$$n$$$ steps. During $$$i$$$-th step he wants to move the book number $$$b_i$$$ into his backpack. If the book with number $$$b_i$$$ is in the stack, he takes this book and all the books above the book $$$b_i$$$, and puts them into the backpack; otherwise he does nothing and begins the next step. For example, if books are arranged in the order $$$[1, 2, 3]$$$ (book $$$1$$$ is the topmost), and Vasya moves the books in the order $$$[2, 1, 3]$$$, then during the first step he will move two books ($$$1$$$ and $$$2$$$), during the second step he will do nothing (since book $$$1$$$ is already in the backpack), and during the third step — one book (the book number $$$3$$$). Note that $$$b_1, b_2, \dots, b_n$$$ are distinct.

Help Vasya! Tell him the number of books he will put into his backpack during each step.

Input format:
The first line contains one integer $$$n~(1 \le n \le 2 \cdot 10^5)$$$ — the number of books in the stack.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n~(1 \le a_i \le n)$$$ denoting the stack of books.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n~(1 \le b_i \le n)$$$ denoting the steps Vasya is going to perform.

All numbers $$$a_1 \dots a_n$$$ are distinct, the same goes for $$$b_1 \dots b_n$$$.

Output format:
Print $$$n$$$ integers. The $$$i$$$-th of them should be equal to the number of books Vasya moves to his backpack during the $$$i$$$-th step.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The first example is described in the statement.

In the second example, during the first step Vasya will move the books $$$[3, 1, 4]$$$. After that only books $$$2$$$ and $$$5$$$ remain in the stack ($$$2$$$ is above $$$5$$$). During the second step Vasya will take the books $$$2$$$ and $$$5$$$. After that the stack becomes empty, so during next steps Vasya won't move any books.

Example input:
3
1 2 3
2 1 3

Example output:
2 0 1

Example input:
5
3 1 4 2 5
4 5 1 3 2

Example output:
3 2 0 0 0

Editorial:
Let's maintain the pointer $$$pos$$$ to the topmost non-deleted book and whether each book whether is removed from the stack or not. Initially, all books are in a stack, and $$$pos$$$ is 0 (if we store the array 0-indexed). We will process the array $$$B$$$ in the order $$$b_1, b_2, \dots b_n$$$. If the current book $$$b_i$$$ is removed from the stack, then the answer for it is zero. Otherwise, we will increment the pointer $$$pos$$$ until the equality $$$a_{pos} = b_i$$$ is satisfied, while marking all the intermediate books in the array $$$u$$$. After that, the answer for the book $$$b_i$$$ will be the number of marked books in the $$$u$$$ array (including itself).
Since the pointer $$$pos$$$ shifts $$$n$$$ times at total, we get a solution with an $$$O(n)$$$ complexity.