Адаптивный поиск
(Время: 2 сек. Память: 16 Мб Сложность: 65%)
Знаменитая компания "Gold&Silver Soft" решила занять ведущее место в области разработки реляционных баз данных. Руководство компании понимает, что для этого необходимо удивить потребителей быстродействием своего программного продукта.
Ни для кого не секрет, что в основе реляционной базы данных лежит таблица, которую можно рассматривать как одномерный массив записей. Известно, что при поиске все записи таблицы просматриваются последовательно, начиная с самой первой и заканчивая найденной.
Технический отдел компании установил, что часто бывает так, что поиск одной и той же записи в таблице производится несколько раз. Основываясь на этом, программисты решили после каждого нового поискового запроса менять порядок следования записей в таблице. Другими словами, после поиска найденная запись перемещается на первое место в таблице. Очевидно, что чем чаще осуществляется поиск определенной записи, тем ближе она будет к началу таблицы и тем быстрее будет поиск этой записи.
Вашей задачей является написать программу, которая для каждого из M последовательно заданных поисковых запросов будет определять количество просмотренных записей при поиске заданной. Для простоты обозначения будем считать, что имеется таблица с N записями, где запись – это число от 1 до N. В начале все записи в таблице расположены в порядке возрастания, то есть на i-м месте в таблице находится число i. Для приведенного ниже примера при M = 2, N = 6 и запросах на поиск чисел «5» и «3» потребуется 5 и 4 просмотра записей соответственно.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N и M (1 ≤ N, M ≤ 65535) — количество записей в таблице и количество запросов на поиск соответственно. Числа разделены одиночным пробелом.
Вторая строка содержит M натуральных чисел Ai (1 ≤ Ai ≤ N), разделенных одиночными пробелами, где Ai — запрос на поиск числа Ai в таблице. Запросы на поиск выполняются последовательно в порядке их ввода.
Выходные данные
Единственная строка выходного файла OUTPUT.TXT должна содержать M натуральных чисел, разделенных одиночными пробелами, i-е число – это количество просмотренных записей при поиске числа Ai.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 6 2
5 3 | 5 4 |
| 2 | 10 10
10 9 8 7 6 5 4 3 2 1 | 10 10 10 10 10 10 10 10 10 10 |
| 3 | 3 14
3 2 3 3 1 1 2 2 1 1 1 1 2 1 | 3 3 2 1 3 1 3 1 2 1 1 1 2 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
