codeforces-scrape

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

706B.md (1873B)


      1 Source: https://codeforces.com/problemset/problem/706/B
      2 
      3 B. Interesting drink
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Vasiliy likes to rest after a hard work, so you may often meet him in some bar nearby. As all programmers do, he loves the famous drink "Beecola", which can be bought in *n* different shops in the city. It's known that the price of one bottle in the shop *i* is equal to *x**i* coins.
     22 
     23 Vasiliy plans to buy his favorite drink for *q* consecutive days. He knows, that on the *i*-th day he will be able to spent *m**i* coins. Now, for each of the days he want to know in how many different shops he can buy a bottle of "Beecola".
     24 
     25 Input
     26 
     27 The first line of the input contains a single integer *n* (1 ≤ *n* ≤ 100 000) — the number of shops in the city that sell Vasiliy's favourite drink.
     28 
     29 The second line contains *n* integers *x**i* (1 ≤ *x**i* ≤ 100 000) — prices of the bottles of the drink in the *i*-th shop.
     30 
     31 The third line contains a single integer *q* (1 ≤ *q* ≤ 100 000) — the number of days Vasiliy plans to buy the drink.
     32 
     33 Then follow *q* lines each containing one integer *m**i* (1 ≤ *m**i* ≤ 109) — the number of coins Vasiliy can spent on the *i*-th day.
     34 
     35 Output
     36 
     37 Print *q* integers. The *i*-th of them should be equal to the number of shops where Vasiliy will be able to buy a bottle of the drink on the *i*-th day.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 5  
     45 3 10 8 6 11  
     46 4  
     47 1  
     48 10  
     49 3  
     50 11
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 0  
     57 4  
     58 1  
     59 5
     60 ```
     61 
     62 Note
     63 
     64 On the first day, Vasiliy won't be able to buy a drink in any of the shops.
     65 
     66 On the second day, Vasiliy can buy a drink in the shops 1, 2, 3 and 4.
     67 
     68 On the third day, Vasiliy can buy a drink only in the shop number 1.
     69 
     70 Finally, on the last day Vasiliy can buy a drink in any shop.