Module: SPARSE TABLE


Problem

1 /2


Minimum on segment of immutable array

Theory Click to read/hide

Error

Problem

You are given an array A [1…N]. It is required to perform M calculation of the minimum element on the segment from L to R.

Input
The first line contains the number N (\(1 <= N <= 100000\)) – array size. The second line contains N numbers – array elements. The third line contains the number M (\(1 <= M <= 100000\)) – minimum number of requests. The next M lines contain pairs of numbers L and R (\(L <= R < = N\)) describing segments.

Imprint
For each query print the value of the minimum on the segment separated by a space.

 

Examples
# Input Output
1 5
3 1 8 7 9
2
1 3
3 5 		1 7

time 250 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!