Sections > Unsorted > problem:

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

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 65536/65536/65536/65536 Kb.

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

Дан отсортированный массив, содержащий 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

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

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