402377: GYM100739 K Easy vector

You're given a vector with n elements. Piro starts from cell 1. He walks x seconds. In each second, he can move to an adjacent cell: for a cell i with 2 ≤ i ≤ n, he can move to i - 1 and i + 1. From cell 1 he can only move to cell 2 and from cell n he can only move to cell n-1.

Initially, his sum is what's written on cell 1, from where he starts. Next x seconds, his sum increases by what's written on each cell he visits during those x seconds. What's the maximum sum he can get? Formally, given vector A, choose i₁, i₂, ..., i_x such as you maximize the sum A[1] + A[i1] + A[i2] + ... + A[ix], where 1 ≤ i_k ≤ n and |i_k - i_k - 1| = 1.

Given an array and q queries, each query containing a value x, please answer all of them!

The first line contains numbers n and q (1 ≤ n, q ≤ 10⁵, n is at least 2). Next n lines contain the values of vector: each element of vector is between 1 and 10⁵. Next q lines contain values of queries: each lines contains a new value for x (1 ≤ x ≤ 10⁹).

Output q lines, containing the answers for each query.

3 2
5 2 1
1
2

7
12