feruz.atamuradov's blog

By feruz.atamuradov, history, 7 years ago, In Russian

Hi CF community. I found problem tag of binary indexed tree. I have not any ideas. Help me!
TASK

(Time: 2 seconds Memory: 16 MB)

The famous company "Gold & Silver Soft" decided to take the leading place in the field of development of relational databases. The management of the company understands that for this it is necessary to surprise consumers with the speed of their software product.

It's no secret that the relational database is based on a table that can be considered as a one-dimensional array of records. It is known that when searching all records of the table are viewed sequentially, starting with the very first and ending with the one found.

The technical department of the company has established that it often happens that the search for the same record in the table is made several times. Based on this, the programmers decided after each new search query to change the order of the records in the table. In other words, after searching, the found entry is moved to the first place in the table. Obviously, the more often a specific record is searched, the closer it will be to the beginning of the table and the faster the search for that record will be.

Your task is to write a program that for each of the M consecutive search queries will determine the number of scanned records when searching for a given one. For the sake of simplicity, we assume that there is a table with N records, where the record is a number from 1 to N. At the beginning, all records in the table are arranged in ascending order, i.e., the i-th place in the table contains the number i. For the example below, for M = 2, N = 6, and requests for the search for the numbers "5" and "3", you will need 5 and 4 viewing the records, respectively.Tests have in task.

Input

The first line of the input file INPUT.TXT contains two integers N and M (1 ≤ N, M ≤ 65535) — the number of records in the table and the number of search requests, respectively. The numbers are separated by a single space.

The second line contains M natural numbers Ai (1 ≤ Ai ≤ N) separated by single spaces, where Ai is a query to find the number Ai in the table. Search requests are executed sequentially in the order in which they are entered.

Output

The only output line OUTPUT.TXT must contain M natural numbers separated by single spaces, the i-th number is the number of scanned records when searching for the number Ai.

Thanks in advance!

  • Vote: I like it
  • -11
  • Vote: I do not like it