codeforces-1073B Vasya and Books

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

Vasya wants to move all the books to his backpack in n steps. During -th step he wants to move the book number bi into his backpack. If the book with number bi is in the stack, he takes this book and all the books above the book bi, 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 book1 is already in the backpack), and during the third step — one book (the book number 3). Note that  are distinct.

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

Input

The first line contains one integer (1≤n≤2⋅10^5) — the number of books in the stack.

The second line contains n integers  denoting the stack of books.

The third line contains n integers  denoting the steps Vasya is going to perform.

All numbers a1…an are distinct, the same goes for 

Output

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.

Examples

input

Copy
3
1 2 3
2 1 3

output

Copy
2 0 1 

input

Copy
5
3 1 4 2 5
4 5 1 3 2

output

Copy
3 2 0 0 0 

input

Copy
6
6 5 4 3 2 1
6 5 3 4 2 1

output

Copy
1 1 2 0 1 1 
Note

The first example is described in the statement.

In the second example, during the first step Vasya will move the books . After that only books  and  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.

思路:模拟题,关键在于标记数组,标记后的直接跳过。题目说是栈结构,但实际上用这个结构复杂度比直接开数组模拟要大。

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
const int inf=300000;
int arr[inf];
int need[inf];
bool visited[inf];
int output[inf];
int main()
{
  int n=0;
  cin>>n;
  int temp=0;
  for(int i=0;i<n;i++)
    scanf("%d",&arr[i]);
  for(int i=0;i<n;i++)
    scanf("%d",&need[i]);
  int j=0;
  output[0]=1;
  for(int i=0;i<n;i++)
  {
    if(visited[need[i]]) continue;
    while (need[i]!=arr[j])
    {
      output[i]++;
      visited[arr[j]]++;
      j++;
    }
  }
  for(int i=0;i<n;i++)
  {
    printf("%d ",output[i]);
  }

}

 

 

发表评论

电子邮件地址不会被公开。