#808. 圈圈画圈圈

圈圈画圈圈

Joanh_LanJoanh\_Lan最近在学数论,但ta非常的joker迷迷糊糊的他遇见了一个问题,现在ta想向你寻求帮助,如果你可以帮助ta解决这个问题,ta将摆脱joker并变得聪明

因为ta很迷,所以问题的背景环境是一个圆形跑道!

你可以操作跑道上任何一个位置,沿着一个方向行走,在行走距离 aia_i 后有另外一个虚拟人。 你可以沿着圆周,从任意方向行走,这样我们就得到一个环状的跑道。 请你在跑道中找到一条路径,使得每个虚拟人恰好被Joanh_Lan访问一次,且路径长度最短. 请你输出这个最短路径的长度。

输入格式

输入第一行,两个整数,CC, nn,分别代表跑道的周长以及虚拟人的个数.

输入第二行,nn 个递增的整数 aia_i ,代表每个节点在圆上的相对位置.

2C106,2n2×1052 \leq C \leq 10^6, 2\leq n \leq 2 \times 10^5

00 \leq a1a_1 << a2a_2 ... << ana_n <C< C

输出格式

样例输入

20 3
5 10 15

样例输出

10