Submit solution

Points:
10 (partial)

Time limit:
0.5s

Java
1.0s

Memory limit:
64M

Java
64M

Problem type

Roger is training for CCO and has decided to practice implementing segment trees. He decides to solve a classic problem that is solvable with segment trees.

Given an array with integers and subarray queries, compute the range of each subarray.

#### Constraints

The elements of the array are positive integers up to a million.

#### Input Specification

The first line contains two integers, and .

Each of the next lines contains a single integer. These lines constitute the values of the array in order.

Each of the next lines contains two integers, and , indicating a 1-indexed query.

#### Output Specification

For each query, print on a separate line the range of the subarray with leftmost index and rightmost index .

#### Sample Input

```
6 3
1
7
3
4
2
5
1 5
4 6
2 2
```

#### Sample Output

```
6
3
0
```

## Comments