Maximum Profit in Project Selection

You are given a list of projects, each with an associated profit (which may be negative). For each query, you are asked to compute the maximum profit obtainable from a contiguous subsequence of projects within a specified range. In formal terms, for every query with indices \(S\) and \(E\) with \(1 \leq S \leq E \leq N\), you need to compute:

[ \text{max_profit} = \max_{S \leq i \leq j \leq E} \left( \sum_{k=i}^{j} P[k] \right) \quad \text{with the convention that if all sums are negative, the profit is } 0. ]

This is essentially the maximum subarray sum problem for a given segment of the list. Use efficient algorithms like Kadane's algorithm to solve this problem.

inputFormat

The input is given via standard input and has the following format:

1. The first line contains a single integer \(N\) representing the number of projects.
2. The second line contains \(N\) space-separated integers \(P[1], P[2], \ldots, P[N]\) where \(P[i]\) is the profit of the \(i\)-th project.
3. The third line contains a single integer \(Q\) representing the number of queries.
4. Each of the following \(Q\) lines contains two space-separated integers \(S\) and \(E\) representing the start and end indices (1-indexed) for a query.

outputFormat

For each query, output a single line containing the maximum profit that can be obtained from a contiguous subsequence within the specified range. If all sums are negative, output 0.

## sample

5
-1 2 3 -4 5
1
1 3

5

</p>