Flowers#11791
Sign in

Flowers

1 second
256 megabytes
Easy

You want to give Lucy a bouquet of flowers for TimDee, and you have flowers, where the beauty of the -th flower is a_i.

A bouquet can be any contiguous subsequence of the flowers. Let \operatorname{beauty}(l, r) denote the beauty of the subsequence from to .

function beauty(l, r):
    if l == r:
        return a[l]
    
    // choose any m such that l ≤ m < r
    return beauty(l, m) - beauty(m + 1, r)

You are given queries, where each query consists of two integers and . For each query, output the maximum possible value of \operatorname{beauty}(l, r).

Input

The first line contains two integers (1 \le n \le 5 \cdot 10^5) and (1 \le q \le 5 \cdot 10^5) — the length of array and the number of queries.

The second line contains integers a_i (-10^9 \le a_i \le 10^9) — the elements of the array .

Each of the next lines contains two integers l_i, r_i (1 \le l \le r \le n) — the parameters of the -th query.

Output

Output lines, each containing exactly one integer — the answer to the corresponding query.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first example, for the first query we can use the following strategy:

f(1,3) = f(1,1) - f(2,3) = f(1,1) - (f(2,2) - f(3,3)) = 11

For the second query:

f(1,4) = f(1,1) - f(2,4) = f(1,1) - (f(2,3) - f(4,4)) = f(1,1) - ((f(2,2) - f(3,3)) - f(4,4)) = 12

It can be shown that this is the best answer for each query.

Scoring

  1. ( points): n, q \le 10;\ a_i \le 100 for all 1 \le i \le n;

  2. ( points): r_i - l_i \le 3 for all 1 \le i \le q;

  3. ( points): r_i - l_i \le 4 for all 1 \le i \le q;

  4. ( points): r_i - l_i \le 5 for all 1 \le i \le q;

  5. ( points): n, q \le 500;

  6. ( points): n, q \le 500000;