## COCI '22 Contest 5 #3 Logaritam

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type Hrvoje has recently learned about the logarithm function. He really likes the property for each pair of positive real numbers and .

He is actually not interested in the function itself, but in logarithmic sequences. A logarithmic sequence of length is a sequence of real numbers for which holds for every pair of positive integers and such that . An example of a logarithmic sequence of length is .

For his homework, Hrvoje needed to write logarithmic sequences of length . However, after a long night of effort, he woke up to find that Matej had changed exactly one element of each sequence. Hrvoje doesn't have a lot of time to correct his homework, so he is interested in the least number of elements of each sequence he needs to change so the sequence becomes logarithmic again. Unfortunately, Matej had written his element with a pen, so Hrvoje cannot change that element of the sequence.

Hrvoje has forgotten which sequences he wrote for his homework so the only thing he knows is the number of sequences , the length of each sequence and the position of the element Matej had changed in the -th sequence.

Note: It can be proven that for any starting logarithmic sequence the minimal number of changes is the same.

#### Input Specification

In the first line there are two positive integers and  , the length of each sequence and the number of sequences.

In the -th of the next lines there is a positive integer  , the index of the element Matej had changed in the -th sequence.

#### Output Specification

In the -th line, output -1 if Hrvoje cannot change the other elements of the -th sequence such that the sequence becomes logarithmic again. Otherwise, output the minimal number of changes needed to make the sequence logarithmic again.

#### Constraints

1 19 , 2 26 3 29 #### Sample Input 1

6 6
1
2
3
4
5
6

#### Sample Output 1

-1
2
1
2
0
1

#### Explanation for Sample 1

If the starting sequence was and Matej changes the fourth element to , Hrvoje can change the second element to and the sixth to , after which, the sequence will be logarithmic again.

#### Sample Input 2

20 5
7
8
2
19
12

#### Sample Output 2

1
9
9
0
5

#### Sample Input 3

10000 4
1234
2345
3456
7890

#### Sample Output 3

15
148
3332
37