URI Online Judge | 2706
# Linearville

**Timelimit: 1**

By Guilherme A. Pinto, ACM ICPC 2017 Brazil

The city of Linearville has **N** parallel two-way streets going in the West-East direction and **N** parallel two-way streets going in the South-North direction, making up a grid with (**N** − 1) × (**N** − 1) blocks. The distance between two consecutive parallel streets is either 1 or 5. The Linearville Transit Authority is conducting an experiment and now requires all cars to always follow a path that alternates direction between W-E and S-N at every crossing, meaning they must turn either left or right when reaching a crossing. The LTA is developing a new navigation app and needs your help to write a program to compute the lengths of shortest alternating paths between many pairs of start and target crossings. The alternating path in the figure, as an example for **N** = 10, is clearly not a shortest alternating path. But beware! Linearville may be huge.

The first line contains an integer **N** (2 ≤ **N** ≤ 10^{5} ) representing the number of streets in each direction. For each direction, the streets are identified by distinct integers from 1 to **N** starting at the S-W corner of the city. The second line contains** N** − 1 integers **D _{1}**,

Output **Q **lines, each line with an integer indicating the length of a shortest alternating path for the corresponding query of the input.

Input Samples | Output Samples |

10 5 1 5 5 5 1 1 5 5 1 5 5 5 1 5 5 1 5 3 4 3 9 10 9 2 2 9 5 1 5 10 |
46 50 49 |

5 5 1 5 5 5 1 5 5 2 3 1 4 5 5 5 5 5 |
23 0 |