Не час для ігор

У колі стоять $n$ людей, люди з індексами $i$ та $i+1$ є сусідами для кожного $1\le i<n$, і люди з індексами $1$ та $n$ є сусідами. Кожна людина має рівень навичок виражений цілим числом $a_i$. Сусіди утворюють пару з рівнем навичок $a_i+a_{i+1}$. На жаль, вони всі — зайняті люди, таким чином $i$-та людина покидає коло у момент часу $i$. Коли людина $i$ покидає коло, то індекси не зміщаються. Тобто, якщо були пари $(i-1;i)$ та $(i;i+1)$, то після виходу $i$-го не буде утворена пара $(i-1;i+1)$.

Вам дано $q$ запитів, кожен з них містить одне ціле число $t$. На кожен запит треба вивести одне ціле число — максимальне значення рівня навичок, яке можна утворити з людей, які залишись на момент часу $t$.

Вхідні дані

Перший рядок містить два цілі числа $n$ ($2\le n\le 2\cdot 10^5$) та $q$ ($1\le q\le 2\cdot 10^5$) — початкова кількість людей у колі та кількість запитів.

Другий рядок містить $n$ цілих чисел $a_i$ ($1\le a_i\le 10^6$) — значення рівня навичок $i$-ї людини.

Наступні $q$ рядків містять одне ціле число $t$ ($0\le t<n-1$).

Вихідні дані

Виведіть $q$ рядків, $i$-тий з яких містить відповідь на $i$-тий запит.

Приклади

Примітка

Пояснення до першого прикладу:

Перший запит має $t$ = $1$. Позначимо за $X$ тих, хто покинув коло, отже, будемо мати $\{X,1,4\}$. Існує одна пара з другого та третього елементу — $1$ + $4$ = $5$.

Другий запит має $t$ = $0$. Ніхто ще не встиг покинути коло, маємо $\{2,1,4\}$. Існують три пари — перший з другим, другий з третім та третій з першим. Їхні рівні навичок дорівнюють $2$ + $1$ = $3$, $1$ + $4$ = $5$ та $4$ + $2$ = $6$ відповідно.