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

Разделы > Неотсортированные > задача:


Правый двоичный поиск

Задачи раздела

• Порядковая статистика
• Порядковая статистика — 2
• Последовательность
• Постиранный пароль
• Постфиксное выражение
• Почти совершенная задача
• Почтовые цифры
• Почтовый принтер
• Правый двоичный поиск
• Принтеры
• Проверка на простоту — 1
• Проверка на простоту — 2
• Проверка решений
• Программируем роботов: кран
• Пропущенные цифры
• Простая игра в кегли
• Простой калькулятор

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

Если у вас есть предложения или пожелания по работе 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
Выходные данные
1
Входные данные
10
1 1 1 3 3 3 3 3 4 4
3
4 4 1
Выходные данные
20
Входные данные
10
2 2 7 7 7 7 8 8 8 10
5
7 6 9 1 1
Выходные данные
1
Для отправки решений необходимо выполнить вход.

www.contester.ru