The 2880 algorithms club went to Corani and is now preparing firewood for the fireplace. The little wood logs are cylindrical and stacked in the shape of a triangular pyramid: there are $$$N$$$ logs at the base, $$$N-1$$$ in the next row, and so on until a single log at the top.
Pakai came up with the idea of playing by removing logs from the base and discovered an interesting problem. Each log in an upper row rests on the two logs immediately below it. If it loses either of its two supports, it falls. This can make other logs fall in a chain reaction. Fallen logs are removed from the pile without hitting or displacing the others.
Pakai will remove $$$Q$$$ logs from the base, one by one, waiting for all the falls to finish after each removal. The positions of the base are numbered from $$$1$$$ to $$$N$$$, from left to right, and keep their original numbering throughout the whole process (fallen or removed logs never return to the pile).
How many logs remain in the whole pyramid after each removal?
The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N \leq 10^{9}$$$; $$$1 \leq Q \leq \min(N, 2 \times 10^{5})$$$).
Each of the following $$$Q$$$ lines contains an integer $$$p_i$$$ ($$$1 \leq p_i \leq N$$$): the position of the base log that Pakai removes in operation $$$i$$$. All positions $$$p_i$$$ are pairwise distinct.
Print $$$Q$$$ lines. On line $$$i$$$, write the total number of logs that remain in the whole pyramid after operation $$$i$$$ (that is, after removing $$$p_i$$$ and all the falls that this removal causes).
5 3315
6 4 2
6 216
15 10
Explanation for example 1
Initially there are $$$15$$$ logs. After removing the one at position $$$3$$$, two intact stretches of two positions each remain (positions $$$1,2$$$ and $$$4,5$$$), which support $$$3+3=6$$$ logs. After removing the one at position $$$1$$$, the left stretch is reduced to position $$$2$$$ alone and $$$1+3=4$$$ logs remain. Finally, after removing the one at position $$$5$$$, only the base logs at positions $$$2$$$ and $$$4$$$ survive, each one supporting only itself: $$$1+1=2$$$ logs.
Explanation for example 2
This case illustrates the ends of the base. Initially there are $$$21$$$ logs. After removing position $$$1$$$ (the left end), a single stretch with positions $$$2,\ldots,6$$$ survives, which supports $$$15$$$ logs. After then removing position $$$6$$$ (the right end), the stretch $$$2,\ldots,5$$$ survives, which supports $$$10$$$ logs.
