Remote Training on Programming

Спам - это нежелательная (обычно рекламная) корреспонденция, которая приходит в ваш электронный почтовый ящик. Современные почтовые сервисы, такие как Google Mail, более-менее успешно справляются с автоматическим удалением спама.

Сигизмунд − начинающий предприниматель, который уверен, что его алгоритм узнавания спама работает лучше общеизвестных. Он хочет продать его ведущим IT-компаниям и заработать много денег.

На вход алгоритму подается список писем для проверки. Для каждого письма алгоритм выставляет оценку − натуральное число в диапазоне от 1 до 10⁹. Чем больше оценка, тем более вероятно, что письмо является спамом.

Казалось бы, алгоритм готов, и дело сделано. Однако, Сигизмунд осознал, что не всё так просто. Для алгоритма необходимо ещё определить порог срабатывания − то есть выше какой оценки письмо будет считаться спамом, чтобы можно было его автоматически удалить.

Для этого Сигизмундом была подготовлена обучающая выборка, состоящая из N писем. Все эти письма были им просмотрены вручную, и для каждого письма отмечено, является ли оно спамом, или нет.

Вам необходимо помочь Сигизмунду выбрать правильный порог для отсеивания спама на основе обучающей выборки. Качество отсеивания будет определяться метрикой F₁, которая вычисляется по формуле

F₁ = 2 ∙ precision ∙ recall / (precision + recall)

В случае, когда precision и recall равны нулю, считается, что F₁ тоже равна нулю.

Метрика precision для порога t равна отношению числа спам-писем со значением оценки ≥ t к числу всех писем со значением оценки ≥ t.

Метрика recall для порога t равна отношению числа спам-писем со значением оценки ≥ t к общему числу всех спам-писем безотносительно порога.

Ваша задача − рассчитать значение порога t (натуральное число, большее или равное единице), которое даёт максимальное значение F₁. При наличии нескольких различных вариантов t с максимальным значением F₁ необходимо выбрать минимальный t.

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

В первой строке содержится натуральное число N (1 ≤ N ≤ 10⁵) − общее количество писем.

Во второй строке записаны N натуральных чисел через пробел − значение оценки для первого, второго и так далее письма (натуральные числа в диапазоне от 1 до 10⁹).

В третьей строке записано число K (1 ≤ K ≤ N) − количество спам-писем.

В четвёртой строке перечислены K целых чисел через пробел в диапазоне от 1 до N включительно − номера писем, которые являются спамом.

 

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

Выведите одно натуральное число − найденный порог t

Пример ввода 1 5 1 2 3 4 5 3 1 3 4 Пример вывода 1 1

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

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

Решения, верно работающие при  N ≤ 1000, будут оцениваться из 70 баллов