O(n²) Stress Test 2 Range Sum (Non-Random)

Points 100 4.0s 256M

You are given \(n\) numbers \(a_1, a_2, \ldots, a_n\) together with \(n\) queries. In the \(i\)-th query you are given two integers \(x_i, y_i\) with \(x_i \le y_i\); report the sum of the elements whose indices lie between \(x_i\) and \(y_i\) inclusive.

Input

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)).

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(-10^4 \le a_i \le 10^4\)).

Each of the next \(n\) lines contains two integers \(x_i, y_i\) (\(1 \le x_i \le y_i \le n\)).

Unlike the previous task, these test cases are not generated purely at random.

Output

For each query, output a single integer representing the required sum.

Sample Input 1

5
-2493 -7467 2309 -4055 8970
4 5
5 5
2 5
1 3
2 4

Sample Output 1

4915
8970
-243
-7651
-9213

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.