eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Гольф Бот

Гольф Бот

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Вы любите гольф? Я ненавижу. Я так ненавижу гольф, что решил создать идеального робота для гольфа: робота, который никогда не промахнется. Я просто ставлю его у мяча, выбираю правильное направление и расстояние, и он безупречно бьет по мячу который летит по воздуху и попадает прямо в лунку. В гольф больше никогда не будут играть.

К сожалению все идет не так, как планировалось. Итак, вот я стою в зелени и готовлю свой первый удар, когда понимаю, что встроенная ручка выбора расстояния не имеет всех вариантов расстояния! Не все потеряно, так как у меня есть 2 удара.

С учетом моего робота, сколько лунок я смогу заполнить за 2 удара или меньше?

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

В первой строке записано одно целое число n (1n200 000) - количество различных расстояний, на которые гольф-бот может совершать удары. Каждая из следующих n строк содержит одно целое число k[i] (1k[i]200 000) - расстояние, отмеченное в позиции i ручки.

В следующей строке стоит одно целое число m (1m200 000) - количество лунок на поле. Каждая из следующих m строк содержит одно целое число d[j] (1d[j]200 000) - расстояние от гольф-бота до лунки j.

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

Выведите одно число - количество лунок, которые сможет пройти Гольф-бот. Гольф-бот не может перебросить мяч через лунку чтобы потом ударить назад.

Пример

Гольф-бот может стрелять на 3 разные дистанции (1, 3 и 5). На поле имеется 6 лунок на расстояниях 2, 4, 5, 7, 8 и 9. Гольф-бот сможет забить мяч в 4 из них:

  • Первая лунка на расстоянии 2 может быть достигнута двумя ударами на расстояние 1.

  • Вторая лунка на расстоянии 4 может быть достигнута ударом 3 и потом ударом 1 (или наоборот).

  • Третья лунка на расстоянии 5 может быть достигнута ударом 5.

  • Пятая лунка на расстоянии 8 может быть достигнута двумя ударами 3 и 5.

Лунка 4 на расстоянии 7 и лунка 6 на расстоянии 9 недостижимы.

Пример

Входные данные #1
3
1
3
5
6
2
4
5
7
8
9
Выходные данные #1
4
Источник 2014 ACM Southwestern Europe Regional Contest (SWERC), Задача C