All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Transaction
Tag(s):

Binary Search, Data Structures, Medium-Hard, Merge Sort, Segment Trees

Problem
Editorial
Analytics

BOB (Bank of Byteland) is the only bank in the land of byteland. Hence million of transactions take place every day. You are currently the manager in charge of BOB. Being bored one day you took all the transaction of that day and asked your friend Codemonk to ask $$Q$$ queries on the data . Codemonk being a exceptionally good coder gave you two numbers $$M $$ and $$N$$. He then asks you to tell him $$N^{th}$$ transaction having cost more than or equal to $$M $$ maintaining the order of transaction if it exist else print $$-1 $$. Can you answer all of his queries.

Input

First line of input contains T and Q i.e number of transaction and number of queries.
Next line contains T intergers representing cost of each transaction.
Next Q lines contains two integers representing M and N.

Output

For each query print the cost of required transaction if it exists else print -1.

Constraints

$$ 1<=T<=100000$$

$$ 1<=Q<=100000$$

$$ 1<=Cost$$ $$of$$ $$ each$$ $$transaction$$ $$<=100000$$

$$1<=M,N<=100000$$

SAMPLE INPUT
5 5
1 2 3 4 5
1 2
2 3
3 1
3 4
4 8
SAMPLE OUTPUT
2
4
3
-1
-1
Explanation

Cost of transactions are {1,2,3,4,5}

1st Query {1,2} :- 2nd number greater than equal to 1 is 2.

2nd Query {2,3} :- 3rd number greater than equal to 2 is 4.

3rd Query {3,1} :- 1st number greater than equal to 3 is 3.

4th Query {3,4} :- Since there are only three numbers greater than equal to 3 hence -1.

5th Query {4,8} :- Since there are only two numbers greater than equal to 4 hence -1.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications