C. Yet Another Card Deck-Educational Codeforces Round 107 (Rated for Div. 2)

Problem - 1511C - Codeforces

C. Yet Another Card Deck

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You have a card deck of nn cards, numbered from top to bottom, i. e. the top card has index 11 and bottom card — index nn. Each card has its color: the ii-th card has color aiai.

You should process qq queries. The jj-th query is described by integer tjtj. For each query you should:

• find the highest card in the deck with color tjtj, i. e. the card with minimum index;
• print the position of the card you found;
• take the card and place it on top of the deck.

Input

The first line contains two integers nn and qq (2≤n≤3⋅1052≤n≤3⋅105; 1≤q≤3⋅1051≤q≤3⋅105) — the number of cards in the deck and the number of queries.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤501≤ai≤50) — the colors of cards.

The third line contains qq integers t1,t2,…,tqt1,t2,…,tq (1≤tj≤501≤tj≤50) — the query colors. It's guaranteed that queries ask only colors that are present in the deck.

Output

Print qq integers — the answers for each query.

Example

input

Copy

7 5
2 1 1 4 3 3 1
3 2 1 1 4

output

Copy

5 2 3 1 5 

Note

Description of the sample:

1. the deck is [2,1,1,4,3–,3,1][2,1,1,4,3_,3,1] and the first card with color t1=3t1=3 has position 55;
2. the deck is [3,2–,1,1,4,3,1][3,2_,1,1,4,3,1] and the first card with color t2=2t2=2 has position 22;
3. the deck is [2,3,1–,1,4,3,1][2,3,1_,1,4,3,1] and the first card with color t3=1t3=1 has position 33;
4. the deck is [1–,2,3,1,4,3,1][1_,2,3,1,4,3,1] and the first card with color t4=1t4=1 has position 11;
5. the deck is [1,2,3,1,4–,3,1][1,2,3,1,4_,3,1] and the first card with color t5=4t5=4 has position 55.

===============================================================================================================

自始至终，我们只需要统计50种以内颜色第一次出现的位置，因为一旦点到这个颜色我们还是要将他放在第一个位置，始终覆盖着和它颜色相同但是位置靠下的卡片。暴力模拟即可。

#include<iostream>
using namespace std;
 
int id[100];
 
int main()
{
 
    int n,t;
 
 
    cin>>n>>t;
 
    for(int i=1;i<=n;i++)
    {
        int x;
 
        cin>>x;
 
        if(!id[x])
            id[x]=i;
 
    }
 
    for(int i=1;i<=t;i++)
    {
        int pos;
 
        int color;
 
        cin>>color;
 
        cout<<id[color]<<" ";
 
        pos=id[color];
 
        id[color]=1;
 
        for(int i=1;i<=50;i++)
        {
            if(i!=color&&id[i]&&id[i]<pos)
            {
                id[i]++;
 
            }
        }
 
    }
 
 
 
    return 0;
 
}