题目描述

译自 COCI 2022/2023 Contest #5 T3「Logaritam」

定义对数序列为一个长为 $n$ 的书序序列 $(a_1,a_2,\ldots,a_n)$，满足对于所有正整数 $x,y$ 且 $xy\le n$，有 $a_{xy}=a_x+a_y$。一个长为 $6$ 的对数序列例子为 $0,1,\pi,2,0.7,1+\pi$。

有 $q$ 个长度为 $n$ 的对数序列，但是现在每个序列都恰好有一个元素被改掉了。给你序列个数 $q$，序列长度 $n$ 和每个序列被改动的元素位置 $x_i$，对于每个序列，输出在不改动已经更改的元素的情况下，至少要修改序列中多少个位置的元素才能使这个序列仍然是对数序列。

注：可以证明对于任意的初始对数序列，改动同一位置后，在不改动这个位置的情况下将序列变为对数序列的最小改动数都是相等的。

输入格式

第一行两个正整数 $n,q\ (1\le n\le 10^8,1\le q\le 10^4)$，分别表示序列长度和序列个数。

接下来 $q$ 行，第 $i$ 行一个正整数 $x_i\ (1\le x_i\le n)$，表示第 $i$ 个序列中修改的元素下标。

输出格式

如果第 $i$ 个序列无法在不改动已经更改的元素的情况下，将原序列变为对数序列，则输出 $-1$，否则输出最少更改元素个数。

6 6
1
2
3
4
5
6

-1
2
1
2
0
1

20 5
7
8
2
19
12

1
9
9
0
5

10000 4
1234
2345
3456
7890

15
148
3332
37

数据范围与提示

详细子任务附加限制及分值如下表所示