6. Anti-fraud
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vasya decided to develop a plugin for the new messenger Min. The plugin should determine whether an incoming message is fraudulent (i.e., written by scammers). Vasya has almost completed the work and implemented an algorithm that gives a score P for each message. The higher this score, the greater the likelihood that the message is fraudulent. The last detail remains — it is necessary to determine the triggering threshold, that is, starting from what threshold value T messages with a score P ≥ T will be considered fraudulent by the algorithm.

To solve this problem, Vasya formed a training dataset of N messages and enlisted the help of his classmates as experts. They read these N messages and marked which of them are fraudulent. All other messages are not fraudulent.

To evaluate the quality of the algorithm, Vasya decided to use the F1 metric. Let's explain how it is calculated. We introduce the following notations:

  • TP (True Positive) — the number of messages that the algorithm recognized as fraudulent and which are actually fraudulent.
  • FP (False Positive) — the number of messages that the algorithm recognized as fraudulent, but which are actually not fraudulent.
  • TN (True Negative) — the number of messages that the algorithm recognized as not fraudulent and which are actually not fraudulent.
  • FN (False Negative) — the number of messages that the algorithm recognized as not fraudulent, but which are actually fraudulent.

Then the values of precision and recall are calculated using the formulas:

precision = TP / (TP + FP), which indicates what proportion of messages that our algorithm labeled as fraudulent are indeed fraudulent.

recall = TP / (TP + FN), which indicates what proportion of fraudulent messages among all fraudulent messages our algorithm found.

The F1 metric is calculated using the formula:

F1 = 2·precision·recall / (precision + recall)

Note: In the case when both precision and recall are zero, the resulting F1 metric is also zero.

The larger the value of the F1 metric, the higher the quality of classification. Find such a natural number — the threshold value T, which gives the maximum value of F1.

Input

The first line of the input data contains the number N (1 ≤ N ≤ 105) — the total number of messages.

The second line lists N natural numbers separated by spaces in the range from 1 to 109 — the score values P for each message.

The third line contains the number K (1 ≤ K ≤ N) — the number of fraudulent messages.

The fourth line lists K distinct integers in the range from 1 to N in arbitrary order — the indices of the fraudulent messages.

Output

Output a single natural number — the threshold value T, at which the maximum value of the F1 metric is achieved. If there are multiple correct answers, output the smallest one.

Examples
Input
5
1 2 3 4 5
3
1 4 3
Output
1
Input
10
1 2 3 4 5 6 7 8 100 1000
1
9
Output
9
Note

Note for Python users. To input a set of space-separated integers, you can do it like this: 

a = [int(x) for x in input().split()]

Grading system.

Subtask 1 (up to 60 points): N ≤ 100.

Subtask 2 (up to 40 points): N ≤ 105.