408303: GYM103091 C Meta Frequency
Description
Stanford's football team is doing end-of-year performance reviews. Coach Sao is very upset with his team members for being late to practice! There are $$$S$$$ players on the team, numbered $$$1$$$ to $$$S$$$, and every time a player is late, he writes their number on the whiteboard. Looking at the whiteboard, they have been late $$$N$$$ times in total.
Coach Sao has decided to make the players do push-ups as punishment. Player $$$k$$$ has to count how many total times the players numbered $$$1$$$ to $$$k$$$ have been late, and then do that number of push-ups. MTL is wondering whether Coach Sao is too cruel to his players, so he asks him, "How many players do at most $$$x$$$ push-ups?" MTL is very forgetful, so he may ask Coach Sao up to $$$Q$$$ questions. He may ask multiple questions with the same $$$x$$$. Since $$$Q$$$ and $$$x$$$ may be large, help Coach Sao answer these questions!
InputThe first line contains two space separated integers, $$$S$$$ and $$$N$$$ ($$$1 \leq S \leq 10^9$$$, $$$1\leq N \leq 10^5$$$).
The second line contains $$$N$$$ space-separated integers: the numbers on the whiteboard.
The third line contains an integer $$$Q$$$, ($$$1 \leq Q \leq 10^5$$$) the number of questions MTL will ask.
The next $$$Q$$$ lines represent the questions. Each question will be the integer $$$x$$$, ($$$0 \leq x \leq 10^9$$$) on one line.
OutputFor every question, output the answer in one line.
ExampleInput4 6 1 2 4 2 2 1 2 1 3Output
0 1