P5582 「SWTR-1」Escape

有一天，当 $\mathrm{Sunny}$ 闲逛的时候，发现了一个按钮。 好奇心驱使他按下了这个按钮。 突然间，天旋地转 $\dots$

醒来之后，$\mathrm{Sunny}$ 发现自己站在一个奇怪的地方。 这个地方有 $n$ 个平台，**形成了一个环**。 这时，$\mathrm{Ethan}$ 的声音响起： “哈哈哈哈哈哈，恭喜你，你是第一个来到**死亡之地**的人。” “正如你所看到的，这个地方有 $n$ 个平台，你现在站在 $0$ 号平台上。” “剩余平台按顺时针编号 $1,2,3\dots n-1$，也就是说，你身后的那个平台就是 $n-1$ 号平台。” “你每次能够**顺时针**跳 $i$ 个平台，$i\in[1,n]$，每次的 $i$ 可以不一样。” “如果你能够经过所有平台（初始 $0$ 号位置不算），那你就能逃出**死亡之地**了。” （这里指的是一开始的 $0$ 号位置不算经过，需要再次经过 $0$ 号位置） “不过，这样太简单了，我会给你一些数 $a_j$，表示你**不能一次顺时针跳 $a_j$ 个平台**。” “还有，你必须要用**最少**的跳跃次数完成我的任务。” “如果你不能满足我的上面两个要求，所有平台就会消失，你将会掉入下面的岩浆之中。” 现在，$\mathrm{Sunny}$ 想知道他是否可能逃出这个地方。 如果不行，输出```-1```，否则输出他最少所需的跳跃次数。 因为 $\mathrm{Sunny}$ 觉得死亡之地实在是太有趣了，所以他决定多玩几次，**多组数据**。

无

无

--- ### 样例说明 第一组数据： $\mathrm{Sunny}$ 每次只能顺时针跳 $5$ 个平台，易知不可能完成。 第二组数据： $\mathrm{Sunny}$ 每次只能顺时针跳 $3$ 个平台，跳 $5$ 次即可。 --- ### 数据范围与约定 $0\leq k\leq n\leq 10^6,1\leq n$。 保证 $\sum{n_i}\leq 3*10^6,a_j\leq n$，且**互不相同**。 测试点 $1:5\%,n=1$。 测试点 $2:5\%,n\leq5$。 测试点 $3:10\%,n\leq15$。 测试点 $4:15\%,n\leq300$。 测试点 $5:25\%,n\leq5000$。 测试点 $6:40\%,n\leq10^6$。 --- 梦醒了……