Competitions

# ADA University - March 7 - Segment Tree

# Can you answer these queries - 1

You are given an integer sequence `a`

, _{1}`a`

, ..., _{2}`a`

(|_{n}`a`

| ≤ _{i}**15007** , **1** ≤ **n** ≤ **50000**). A query is defined as follows:

Query(**x**, **y**) = **MAX** {`a`

+ _{i}`a`

+ ... + _{i+1}`a`

, _{j}**x** ≤ **i** ≤ **j** ≤ **y**}

Given **m** queries, your program must output the results of these queries.

#### Input

The first line contains the integer **n**. In the second line **n** integers of the sequence are given. The third line contains the integer **m**. Then **m** lines follow, where line **i** contains two numbers `x`

and _{i}`y`

._{i}

#### Output

Print the results of the **m** queries, one query per line.

Input example #1

3 -1 2 3 1 1 2

Output example #1

2