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.