Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Количество чисел, равное искомому

Бинарный поиск в массиве

Требуется определить в заданном массиве количество элементов, равных искомому числу.

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

В первой строке вводится одно натуральное число N, не превосходящее 105: количество чисел в массиве.

Во второй строке вводятся N натуральных чисел, не превосходящих 109, каждое следующее не меньше предыдущего.

В третьей строке вводится количество искомых чисел M - натуральное число, не превосходящее 106.

В четвертой строке вводится M натуральных чисел, не превосходящих 109.

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

Для каждого запроса выведите в отдельной строке одно число: количество элементов массива, равных числу-запросу. Элементы массива нумеруются с единицы.

Если в массиве нет такого числа, выведите 0.

Примеры
Входные данные Выходные данные
1 4
1 2 2 4
4
1 4 3 2
1
1
0
2