← 返回题目列表

AtCoder · abc160_c

C. 环湖旅行推销员

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有一个圆形池塘,周长为 K 米,以及 N 他们周围有房子。

的 树的 i第一座房子的建造距离为 A_i 距离池塘最北点米,绕池塘顺时针测量。

在这些房屋之间移动时,只能绕着池塘走。

求当您从其中一栋房屋开始并访问所有房屋时需要行驶的最短距离 N 房子。

约束

  • 2 \leq K \leq 10^6
  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_1 < ... < A_N < K
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

K N
A_1 A_2 ... A_N

输出

打印当您从其中一栋房屋出发并访问所有房屋时需要行驶的最短距离 N 房子。


示例输入 1

20 3
5 10 15

示例输出 1

10

如果您从 1-st 房子并前往 2-nd 和 3-按此顺序第 d 个房屋,行驶的总距离将为 10.


示例输入 2

20 3
0 5 15

示例输出 2

10

如果您从 2-nd 房子并前往 1-st 和 3-按此顺序第 d 个房屋,行驶的总距离将为 10.