Sherlock and Numbers
Tag(s):

## Binary search algorithm, Easy, Sorting algorithm

Problem
Editorial
Analytics

Watson gives to Sherlock a bag of numbers [1, 2, 3 ... N] and then he removes K numbers A1, A2 ... AK from the bag. He now asks Sherlock to find the P'th smallest number in the bag.

Input
First line contains T, the number of test cases. Each test case consists of N, K and P followed by K integers in next line denoting the array A.

Output
For each test case, print P'th smallest number in the bag. If no such number exists output -1.

Constraints
1 ≤ T ≤ 10
20% testdata: 1 ≤ N ≤ 103
20% testdata: 1 ≤ N ≤ 105
60% testdata: 1 ≤ N ≤ 109
0 ≤ Kmin(N, 105)
1 ≤ PN

Note: Large input files. Use scanf instead of cin.

SAMPLE INPUT
2
4 1 2
1
5 2 4
1 3

SAMPLE OUTPUT
3
-1

Explanation

Test case 1: Remaining numbers are [2, 3, 4]. 3 is the 2nd smallest remaining numbers.

Test case 2: Remaining numbers are [2, 4, 5]. 4th smallest remaining number doesn't exist.

Time Limit: 2.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: Bash, 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, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

February Love '15

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Algorithms > Dynamic Programming
• Data Structures > Advanced Data Structures
• Basic Programming > Implementation