URI Online Judge | 2120

# Tutors

By Lucca Siaudzionis, University of British Columbia Canada

Timelimit: 1

Every time a new student joins the Educational Organization Farias Brito, he or she gets assigned to a tutor to help him know everyone and everything in the school.

The school’s system to determine each new student’s tutor was designed by a mad man called Succa Liaudzionis. Succa decided to use each student’s ID number to follow the pattern of a binary search tree (because reasons), like this:

1. The first student, with ID X1, becomes the root of the tree and thus has no tutor.
2. The numbers X2, X3, …, Xn are added one by one to the tree. To add a number Xi one must traverse the tree starting from the root and using the following rules:
• The pointer is initially set to the root of the tree.
• If Xi is smaller than the ID of the current node, then its left child becomes the current node. Otherwise, the right child does.
• If at some point the required child does not exist, the new node is created containing the value of Xi. The ID of the tutor of the current student is the parent Xin the tree.

For example, if the order in which the students were added was (3, 1, 4, 2, 5), the tree would look like this:

Succa was in need of extra space in his computer and decided to erase all information regarding the students’ tutors. Now, Succa’s boss, Jeixeira Túnior, asked him for the very same information about Q he had just deleted! Succa consider asking each student who his/hers tutor is, but that would take a lot of time.

On the other hand, Succa still knows the order in which the students were added to tree. Since Succa is not as brilliant as he is mad, he needs your help to use this information to tell him each student’s tutor.

## Input

The input consists of four lines. The first one contains an integer N (2 ≤ N100 000), the number of students in Farias Brito. The second line contains N distinct integers Xi (1 ≤ Xi ≤ 109), representing the students’ ID numbers in the order in which they were added to the system. The third line contains the integer Q (1 ≤ Q99 999). The fourth line contains Q integers from 1 to N representing the students whose tutors are asked (information regarding the first student shall not be requested).

## Output

The output consists of Q integers. The integers represent, in order, the ID numbers the tutors of all students in order in which they were requested.

 Input Samples Output Samples 3 5 1 2 1 2 5
 5 3 1 4 2 5 2 2 5 3 4