配点 : 100 点
問題文
双六在Cybozu员工中很受欢迎。
员工正在玩的双六 N+1 由方块组成,每个方块都有一个按递进顺序排列的数字。 附上 0, 1, ... N 。 起始平方数是 0 ,目标方格的数量为 N 。
您正在练习自己移动棋子以适应这个双六。 在实际移动碎片之前 K 一回合前进的方格数 我决定 a_i (1 \leq i \leq K) 并将棋子放在起始方块上。 我决定按照以下规则实际移动棋子。
i 转 对 (1 \leq i \leq K) 执行的操作
- 件 a_i 如果前进后仍未达到目标,请移动棋子。 a_i 前进。
- 准确放置碎片 a_i 当您推进棋子并到达目标时,移动该棋子。 a_i 前进一个方格到达目标并结束游戏,无需进行任何剩余回合。
- 件 a_i 如果前进不到一格就能到达目标,则到达目标。 x 当可以准确到达该方块时,移动到目标,然后 a_i - x 回去吧。
N 、 K 和 给出了 a_i ,所以最后 (K 当你完成所有回合或中途到达目标并结束游戏时)找到放置棋子的方格的编号。
制約
- 1 \leq N \leq 10^9
- 1 \leq K \leq 1000
- 1 \leq a_i \leq N (1 \leq i \leq K)
入力
输入按以下格式给出。
N K a_1 ... a_K
出力
打印该棋子最终放置的方格的编号。
入力例 1
10 4 5 7 2 5
出力例 1
10
首先,这些作品是 它位于 0 。
- 1 开启 5 出现了,所以这首曲子是 移至 5 。 移至
- 2 开启 7 出现了,所以这首曲子是 移至 10 仍然 2 你可以移动方块,所以 返回到 8 。 我移动到了
- 3 开启 2 出现了,所以这首曲子是 移至 10 ,刚刚到达目标,所以我在这里停止移动。
最后 一块被放置在 10 上。
入力例 2
10 4 5 7 3 5
出力例 2
6
入力例 3
20 7 12 5 5 15 2 10 20
出力例 3
1