Processing math: 100%

Задача M. Хоттабыч и гирлянда tmp

Автор:А. Жуплев   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Однажды под новый год Гассан Абдуррахман ибн Хоттаб решил помочь Вольке нарядить ёлку. Среди ёлочных украшений Хоттабычу больше всего понравилась гирлянда, состоящая из N цветных лампочек. Приглядевшись, Хоттабыч насчитал K различных цветов лампочек.

Хоттабыч вспомнил два своих любимых цвета, нашел пару ближайших друг к другу лампочек первого и второго цветов (порядок лампочек в паре не имеет значения), и подсчитал количество лампочек между ними. Потом он выбрал ещё два цвета и повторил поиск для них... Хоттабычу очень понравилось это занятие, и теперь он просит вас написать программу, которая, получив на входе описание гирлянды и M запросов Хоттабыча, отвечала бы на каждый запрос.

Рекомендуется рассмотреть частичные решения

Формат входного файла

В первой строке входного файла содержится число N.

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

В N+2-й строке входного файла содержится число M.

В последующих 2M строчках содержатся запросы Хоттабыча (по две строки на запрос).

Формат выходного файла

Выходной файл должен содержать M чисел — ответы для каждого запроса в порядке поступления.

Если в запросе указан цвет, отсутствующий на гирлянде, то в качестве ответа следует вывести 1.

Если лампочки обоих цветов есть, но пару найти невозможно, следует вывести 2.

Ограничения

2N15000

1M20000

1K3000

Строка, задающая цвет, состоит из латинских букв, её длина не превышает 255 символов.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10
Red
Green
Blue
Red
Brown
Green
Yellow
Black
Green
Red
6
Red
Green
Blue
Brown
Yellow
Green
Red
Black
Black
Blue
Orange
Green
0
1
0
1
4
-1
2
10
B
C
D
F
G
E
R
C
A
G
3
C
G
R
B
E
E
1 5 -2

0.058s 0.008s 13