codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

368B.md (1455B)


      1 Source: https://codeforces.com/problemset/problem/368/B
      2 
      3 B. Sereja and Suffixes
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Sereja has an array *a*, consisting of *n* integers *a*1, *a*2, ..., *a**n*. The boy cannot sit and do nothing, he decided to study an array. Sereja took a piece of paper and wrote out *m* integers *l*1, *l*2, ..., *l**m* (1 ≤ *l**i* ≤ *n*). For each number *l**i* he wants to know how many distinct numbers are staying on the positions *l**i*, *l**i* + 1, ..., *n*. Formally, he want to find the number of distinct numbers among *a**l**i*, *a**l**i* + 1, ..., *a**n*.?
     22 
     23 Sereja wrote out the necessary array elements but the array was so large and the boy was so pressed for time. Help him, find the answer for the described question for each *l**i*.
     24 
     25 Input
     26 
     27 The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 105). The second line contains *n* integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 105) — the array elements.
     28 
     29 Next *m* lines contain integers *l*1, *l*2, ..., *l**m*. The *i*-th line contains integer *l**i* (1 ≤ *l**i* ≤ *n*).
     30 
     31 Output
     32 
     33 Print *m* lines — on the *i*-th line print the answer to the number *l**i*.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 10 10  
     41 1 2 3 4 1 2 3 4 100000 99999  
     42 1  
     43 2  
     44 3  
     45 4  
     46 5  
     47 6  
     48 7  
     49 8  
     50 9  
     51 10
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 6  
     58 6  
     59 6  
     60 6  
     61 6  
     62 5  
     63 4  
     64 3  
     65 2  
     66 1
     67 ```