Как известно, гориллы — сильные и умные животные. После того, как ученые научили одну из горилл языку программирования Zig, она преисполнилась в своем сознании, выбралась на волю, и объединила всех горилл мира в обществе будущего. Ясно, что свои знания надо передавать следующим поколениям, поэтому горилла основала университет с единственным факультетом, где она преподавала язык Zig и алгоритмы в распределенных системах.
Всего в университет захотели поступить $$$n$$$ горилл, силы горилл равны, соответственно, $$$a_1, \ldots, a_n$$$. Считается, что нет двух равных по силе горилл, поэтому $$$a_i$$$ — различные числа от $$$1$$$ до $$$n$$$.
Поступление организовано следующим образом. Сначала выбирается произвольный отрезок $$$[l, r]$$$ ($$$l \lt r$$$), на котором объявляется, что две самые сильные гориллы поступают в университет. Гориллы не только сильные и умные животные, но еще и самые целеустремленные, поэтому, если хотя бы одна из двух самых сильных горилл находится не на краю отрезка, то ей тут же дают отпор, и она выбывает из конкурса.
Горилла-основатель понимает это, а поэтому старается выбирать для конкурса только честные отрезки, то есть те, в которых два наибольших значения встречаются на границах отрезка. Иными словами, отрезок $$$[l, r]$$$ честный, если $$$\min \{ a_l, a_r \} \gt a_i$$$ для всех $$$l \lt i \lt r$$$. В частности отрезок из двух горилл всегда является честным.
Но пока горилла-основатель думает, как устроить конкурс, остальные гориллы непрерывно тренируются. В итоге это приводит к тому, что в последующие $$$q$$$ часов происходит следующее: в $$$j$$$-й час ($$$1 \le j \le q$$$) горилла с номером $$$x_j$$$ идет в спортивный зал и становится новой самой сильной гориллой, после чего в этот и все последующие часы (до того, как она снова пойдет в спортивный зал) ее сила полагается равной $$$n+j$$$.
Теперь горилла-основатель совершенно запуталась и хочет хотя бы понять, сколько способов у нее будет провести конкурс честно в каждый из моментов времени.
Иными словами для каждого момента времени $$$j$$$ ($$$1 \le j \le q$$$) требуется вычислить количество честных отрезков в момент времени $$$j$$$.
В первой строке заданы два целых положительных числа $$$n$$$ и $$$q$$$ $$$(1 \leq n, q \leq 10^6)$$$ — количество горилл-абитуриентов и количество часов.
Во второй строке находятся $$$n$$$ целых положительных чисел $$$a_1, \ldots, a_n$$$ $$$(1 \leq a_i \leq n)$$$ — силы горилл в начальный момент времени. Гарантируется, что все числа $$$a_i$$$ различны.
В третьей строке находятся $$$q$$$ чисел $$$x_1, \ldots, x_q$$$ $$$(1 \leq x_i \leq n)$$$, где $$$x_j$$$ — номер гориллы, которая идет в спортивный зал в $$$j$$$-й час.
В единственной строке выведите $$$q$$$ чисел, $$$i$$$-е из которых равно количеству честных отрезков в момент времени $$$i$$$.
5 75 1 4 2 31 2 3 1 2 3 5
6 5 5 6 5 5 5
