Binary Search Basic

4.1

38 votes
Easy
Problem

Given an array A of N elements in input. Given Q queries. For each integer X in a query print YES if X is present in given array, print lower_bound and upper_bound of X.
lower_bound of an element is defined as minimum element greater than or equal to X present in array.
upper_bound of an element is defined as minimum element greater than X present in array.

Input
First line contains integer N. Next line contains N space separated integers. Next line contains integer Q (number of queries). Next Q lines contains integer X.

Output
For each query print YES if X is present in array else print NO, print value of lower and upper bound of X. If lower bound and upper bound does not exist print -1.

Constraints
1 <= N <= 105
-109 <= Ai <= 109
1 <= Q <= 105
-109 <= Xi <= 109

Sample Input
6
1 5 4 5 1 9
5
1
3
5
7
9
Sample Output
YES 1 4
NO 4 4
YES 5 9
NO 9 9
YES 9 -1
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?