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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

10
1 1 2 2 3 3 3 3 3 3
1
1

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

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

10
1 1 1 3 3 3 3 3 4 4
3
4 4 1

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

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

10
2 2 7 7 7 7 8 8 8 10
5
7 6 9 1 1

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

Для отправки решений необходимо выполнить вход.

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