6. Антифрод
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася решил разработать плагин для нового мессенджера Min. Плагин должен определять, является ли приходящее сообщение фродом (то есть, что оно написано мошенниками). Вася уже почти выполнил работу и реализовал алгоритм, который для каждого сообщения выдаёт оценку P. Чем больше эта оценка, тем выше вероятность, что сообщение является фродом. Осталась последняя деталь — необходимо определить порог срабатывания, то есть начиная с какого порогового значения T сообщения с оценкой P ≥ T алгоритм будет считать фродом.

Для решения этой задачи Вася сформировал обучающую выборку из N сообщений и привлёк в качестве экспертов своих одноклассников. Они прочитали эти N сообщений и отметили, какие из них — фрод. Все остальные сообщения фродом не являются.

Для оценки качества алгоритма Вася решил использовать метрику F1. Поясним, как она вычисляется. Введём следующие обозначения:

  • TP (True Positive) — количество сообщений, которые алгоритм признал фродом и которые на самом деле — фрод.
  • FP (False Positive) — количество сообщений, которые алгоритм признал фродом, но на самом деле они — не фрод.
  • TN (True Negative) — количество сообщений, которые алгоритм признал не фродом и которые на самом деле — не фрод.
  • FN (False Negative) — количество сообщений, которые алгоритм признал не фродом, но на самом деле они — фрод.

Тогда значения precision (точность) и recall (полнота) вычисляются по формулам:

precision = TP / (TP + FP), то есть какая доля сообщений, которые наш алгоритм назвал фродом, действительно фрод.

recall = TP / (TP + FN), то есть какую долю фрод-сообщений среди всех фрод-сообщений нашёл наш алгоритм.

Метрика F1 вычисляется по формуле:

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

Примечание. В случае, когда precision и recall одновременно равны нулю, результирующая метрика F1 тоже равна нулю.

Чем больше значение метрики F1, тем выше качество классификации. Найдите такое натуральное число — значение порога T, которое даст максимальное значение F1.

Входные данные

В первой строке входных данных записано число N (1 ≤ N ≤ 105) — общее количество сообщений.

Во второй строке перечислены N натуральных чисел через пробел в диапазоне от 1 до 109 — значения оценки P для каждого сообщения.

В третьей строке находится число K (1 ≤ K ≤ N) – количество фрод-сообщений.

В четвертой строке перечислены K различных целых чисел в диапазоне от 1 до N в произвольном порядке — номера фрод-сообщений.

Выходные данные

Выведите одно натуральное число – значение порога T, при котором достигается наибольшеее значению метрики F1. Если есть несколько верных ответов, то выведите наименьший.

Примеры
Входные данные
5
1 2 3 4 5
3
1 4 3
Выходные данные
1
Входные данные
10
1 2 3 4 5 6 7 8 100 1000
1
9
Выходные данные
9
Примечание

Примечание для пишущих на языке Python. Ввести набор записанных через пробел целых чисел можно так: 

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

Система оценивания.

Подзадача 1 (до 60 баллов): N ≤ 100.

Подзадача 2 (до 40 баллов): N ≤ 105.