Երկնաքերներ

Ծովափնյա քաղաքում կա երկնաքերների պողոտա՝ Հարավային պողոտան։ Հարավային պողոտայում շենքերը կառուցված են իրար կպած։ Պողոտան գտնվում է ծովի մակարդակին հավասար բարձրության վրա և ջրի տակ մնալու վտանգի տակ է։ Քաղաքի ղեկավարությունը ցանկանում է տեղեկություն ստանալ պողոտաի մասին ջրի մակարդակի բարձրացման դեպքում։ Տեղեկության գլխավոր մաս է հանդիսանում ջրից բարձր մնացած երկնաքերների խմբերի թիվը. այն երկնաքերները որոնք ջրից բարձր են և իրար կողք են կառուցված համարվում են նույն խմբից։ Տրված են N երկնաքերների բարձրություննէրը և Q հարցում, ամեն հարցումն իրենից ներկայացնում է ջրի մակարդակի բարձրություն։ Ամեն հարցման համար պետք է արտածել չսուզված խմբերի թիվը։

Մուտք

Առաջին տողում տրված է N, Q շենքերի և հարցումների քանակը։

• Թեստերի առաջին խմբի համար $1 ≤ N, Q ≤ 1000$։

• Թեստերի երկրորդ խմբի համար $1 ≤ N, Q ≤ 10^6$։

Երկրորդ տողում տրված են շենքերի բարձրությունները $(0 < a_i \leq 10^9)$ հաջորդաբար։ Երրորդ տողում տրված են հարցումները։

Ելք

Տպել համապատասխանաբար ամեն հարցումի պատասխանը։

Օրինակներ

Աղբյուրը. Հանրապետական 2016