ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Алгоритмы и структуры данных — 2020. Набор задач 2 > задача:


A. Левый двоичный поиск

Алгоритмы и структуры данных — 2020. Набор задач 2

Старт: 18.сен.2020 в 08:00:00
Финиш: 02.окт.2021 в 08:00:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• Подсказки к задачам
• A. Левый двоичный поиск
• B. Правый двоичный поиск
• C. Принтеры
• D. Забор
• E. Все любят уравнения
• F. Ларьки
• G. Лес и поле
• H. Станция

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Левый двоичный поиск
Левый двоичный поиск
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дан отсортированный массив, содержащий N элементов. Элементы массива пронумерованы от 0 до N - 1.

Требуется ответить на M запросов вида «найти индекс первого вхождения числа X в массив».

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

Первая строка содержит целое число N (1 ≤ N ≤ 105) — количество элементов в массиве.

Вторая строка содержит N целых чисел Ai ( - 231 ≤ Ai ≤ 231 - 1) — элементы массива.

Третья строка содержит целое число M (1 ≤ M ≤ 105) — количество запросов.

Четвёртая строка содержит M целых чисел Xi ( - 231 ≤ Xi ≤ 231 - 1) — искомые элементы для каждого запроса.

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

Выведите одно целое число — сумму ответов на все M запросов.

Ответом на i-й запрос является индекс первого вхождения числа Xi в массив, либо -1, если число Xi не содержится в массиве.

Примеры

Входные данные
10
1 1 2 2 3 3 3 3 3 3
1
1
Выходные данные
0
Входные данные
10
1 1 1 3 3 3 3 3 4 4
3
4 4 1
Выходные данные
16
Входные данные
10
2 2 7 7 7 7 8 8 8 10
5
7 6 9 1 1
Выходные данные
-2
Для отправки решений необходимо выполнить вход.

www.contester.ru