Welcome to apply for Zhejiang University.Each ZJU's professor's only admiss one student.And professors' recruitment criteria are different.Professor only recruit the student whoes exam result is between A and B,including A and B.And then professor will choose the student with the highest exam result in these students.Please output this lucky student's exam result.And then the next professor will continue to recruit student from the rest of the students.
The input consists one test case.The first line contains an integer n(n<=300),which means the number of students.The second line contains n integers means the exam results of these n students.As you know,full mark is 500.The third line contains an integer m,which means the number of professors.Then follows m lines,each line contains two integer,A and B(0<=A，B<=500)，which means professor's recruitment criteria.
For each test case, you should output m lines with the recruited student's exam result.If no student meet professor's requirement,you should output -1.