本题真的是

听取WA声一片

1.本题要用 二分！

2.数组要开1e6!蒟蒻调了n小时才发现开的是1e5~~

3.记得加if判断a[r]是不是q

4.输出后要有空格！

附几组 hack 数据：

1

input:

2 3
0 0
0 0 0

output:

1 1 1

2 input:

5
3
2 2 6 9 9
2 9 6

output:

1 4 3

3(用生成器随机生成）

42 126
7 7 9 11 12 13 14 16 19 20 22 23 23 26 28 29 31 32 32 35 35 37 38 40 42 44 46 46 49 50 50 53 53 56 57 59 60 62 62 65 65 67
2 2 5 2 2 6 2 5 5 7 7 4 10 4 7 8 11 5 7 13 9 9 2 11 15 1 5 9 10 15 4 13 11 7 1 13 7 6 20 4 11 13 16 17 19 22 11 16 16 15 14 28 29 9 6 21 30 2 30 20 11 27 26 13 3 30 2 27 18 21 2 31 30 18 35 14 7 5 4 3 25 4 18 31 27 30 21 44 47 46 18 2 31 8 51 5 2 14 45 35 16 42 55 35 15 30 7 39 7 15 51 12 9 1 18 36 44 51 60 31 58 45 49 36 16 39

以上是蒟蒻翻遍十余页讨论版的总结