Submit solution

Points:
10 (partial)

Time limit:
0.3s

Java
0.6s

Memory limit:
64M

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Roger is training for CCO and has decided to practice implementing rage trees. He decides to solve a classic problem that is solvable with rage 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