410187: GYM103969 G Gingerbread House Decorations

Gretel is running a bakery that specializes in mass-producing gingerbread houses! Her bakery is separated into two divisions: one that bakes and assembles the gingerbread pieces and the other which decorates the assembled houses. The latter division is currently dealing with a backlog of $$$10^{18}$$$ gingerbread houses that have yet to be decorated, but is short on workers to frost all of them. Until more help can arrive, Gretel decides to arrange the houses in a horizontal row and assign each of her $$$N$$$ workers to a starting point. Worker $$$i$$$ starts at $$$s_i$$$ (not necessarily unique), which refers to the $$$(s_i)$$$-th leftmost gingerbread house. Each worker can decorate exactly one house per minute, and will move onto decorating the next house to the right regardless of whether or not it is decorated yet. For $$$Q$$$ points in time $$$q_i$$$, Gretel would like to know the number of distinct gingerbread houses that have been decorated at least once after $$$q_i$$$ minutes have elapsed. Can you help her retrieve these counts?

The first line of input contains two space-separated integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N, Q \leq 10^5$$$), representing the number of workers and queries, respectively. The second line of input contains $$$N$$$ space-separated integers $$$s_i$$$ ($$$1 \leq s_i \leq 10^9$$$), representing the starting points of each of the workers on the row of houses. The third line of input contains $$$Q$$$ space-separated integers $$$q_i$$$ ($$$0 \leq q_i \leq 10^9$$$), representing the points in time Gretel would like to know the number of decorated houses.

Output a single line with $$$Q$$$ space-separated integers, representing the answers to Gretel's queries in the order that they were given in.

2 5
5 10
1 2 3 4 5

2 4 6 8 10 

5 10
10 20 30 40 50
11 12 13 14 9 8 7 6 4 3

51 52 53 54 45 40 35 30 20 15