问题

### Instructions: You are an expert Python programmer. You will be given a question (problem specification) and will generate a correct Python program that matches the specification and passes all tests. You will NOT return anything except for the program.
### Question:
The AtCoder Archipelago consists of N islands connected by N bridges.
The islands are numbered from 1 to N, and the i-th bridge (1\leq i\leq N-1) connects islands i and i+1 bidirectionally, while the N-th bridge connects islands N and 1 bidirectionally.
There is no way to travel between islands other than crossing the bridges.
On the islands, a tour that starts from island X_1 and visits islands X_2, X_3, \dots, X_M in order is regularly conducted.
The tour may pass through islands other than those being visited, and the total number of times bridges are crossed during the tour is defined as the length of the tour.
More precisely, a tour is a sequence of l+1 islands a_0, a_1, \dots, a_l that satisfies all the following conditions, and its length is defined as l:

- For all j\ (0\leq j\leq l-1), islands a_j and a_{j+1} are directly connected by a bridge.
- There are some 0 = y_1 < y_2 < \dots < y_M = l such that for all k\ (1\leq k\leq M), a_{y_k} = X_k.

Due to financial difficulties, the islands will close one bridge to reduce maintenance costs.
Determine the minimum possible length of the tour when the bridge to be closed is chosen optimally.

Input

The input is given from Standard Input in the following format:
N M
X_1 X_2 \dots X_M

Output

Print the answer as an integer.

Constraints


- 3\leq N \leq 2\times 10^5
- 2\leq M \leq 2\times 10^5
- 1\leq X_k\leq N
- X_k\neq X_{k+1}\ (1\leq k\leq M-1)
- All input values are integers.

Sample Input 1

3 3
1 3 2

Sample Output 1

2


- If the first bridge is closed: By taking the sequence of islands (a_0, a_1, a_2) = (1, 3, 2), it is possible to visit islands 1, 3, 2 in order, and a tour of length 2 can be conducted. There is no shorter tour.
- If the second bridge is closed: By taking the sequence of islands (a_0, a_1, a_2, a_3) = (1, 3, 1, 2), it is possible to visit islands 1, 3, 2 in order, and a tour of length 3 can be conducted. There is no shorter tour.
- If the third bridge is closed: By taking the sequence of islands (a_0, a_1, a_2, a_3) = (1, 2, 3, 2), it is possible to visit islands 1, 3, 2 in order, and a tour of length 3 can be conducted. There is no shorter tour.

Therefore, the minimum possible length of the tour when the bridge to be closed is chosen optimally is 2.
The following figure shows, from left to right, the cases when bridges 1, 2, 3 are closed, respectively. The circles with numbers represent islands, the lines connecting the circles represent bridges, and the blue arrows represent the shortest tour routes.

Sample Input 2

4 5
2 4 2 4 2

Sample Output 2

8

The same island may appear multiple times in X_1, X_2, \dots, X_M.

Sample Input 3

163054 10
62874 19143 77750 111403 29327 56303 6659 18896 64175 26369

Sample Output 3

390009

### Format: Read the inputs from stdin solve the problem and write the answer to stdout (do not directly test on the sample inputs). Enclose your code within delimiters as follows.
```python
# YOUR CODE HERE
```

### Answer: (use the provided format with backticks)

答案

模型 模型答案 正确答案
金声玉亮2.0 ```python
import sys
input = sys.stdin.read

def solve():
data = input().split()
N = int(data[0])
M = int(data[1])
X = list(map(int, data[2:]))

# Calculate the minimum possible length of the tour
min_length = float('inf')

for i in range(N):
length = 0
for j in range(M - 1):
if X[j] == X[j + 1]:
continue
if X[j] > X[j + 1]:
length += min(X[j + 1] + N - X[j], X[j] - X[j + 1])
else:
length += min(X[j + 1] - X[j], X[j] + N - X[j + 1])
min_length = min(min_length, length)

print(min_length)

solve()
```		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
deepseek-r1

```python
import sys

def main():
N, M = map(int, sys.stdin.readline().split())
X = list(map(int, sys.stdin.readline().split()))

sum_d = 0
diff = [0] * (N + 2) # 1-based to N, +2 for safety

for i in range(M-1):
a = X[i]
b = X[i+1]

delta_forward = (b - a) % N
delta_backward = (a - b) % N
if delta_forward < delta_backward:
d = delta_forward
L = a + 1
R = b
if L > N:
L -= N
if R > N:
R -= N
delta = N - 2 * d
if L <= R:
diff[L] += delta
if R + 1 <= N:
diff[R + 1] -= delta
else:
diff[L] += delta
diff[N + 1] -= delta
diff[1] += delta
if R + 1 <= N:
diff[R + 1] -= delta
else:
d = delta_backward
L = b + 1
R = a
if L > N:
L -= N
if R > N:
R -= N
delta = N - 2 * d
if L <= R:
diff[L] += delta
if R + 1 <= N:
diff[R + 1] -= delta
else:
diff[L] += delta
diff[N + 1] -= delta
diff[1] += delta
if R + 1 <= N:
diff[R + 1] -= delta
sum_d += d

min_total = float('inf')
current = 0
for x in range(1, N+1):
current += diff[x]
total = sum_d + current
if total < min_total:
min_total = total
print(min_total)

if __name__ == '__main__':
main()
```		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE

import sys
import threading

def main():
import sys
import math
sys.setrecursionlimit(1 << 25)
N, M = map(int, sys.stdin.readline().split())
X = list(map(int, sys.stdin.readline().split()))
bridge_usage = [0] * (N + 2)
initial_total_cost = 0

for i in range(M -1):
u = X[i]
v = X[i+1]
delta = (v - u + N) % N
if delta == 0:
continue
elif delta <= N //2:
# Clockwise
initial_total_cost += delta
bridge_usage[u] += 1
bridge_usage[v] -=1
else:
# Counter-clockwise
delta = N - delta
initial_total_cost += delta
bridge_usage[v] +=1
bridge_usage[u] -=1

counts = [0] * (N + 1)
s = 0
min_usage = None
for p in range(1, N+1):
s += bridge_usage[p]
counts[p] = abs(s)

min_usage = min(counts[1:N+1])
total_cost = initial_total_cost + min_usage * (N - 2)
print(total_cost)


threading.Thread(target=main,).start()
```		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
gpt-4o-2024-08-06 ```python
# YOUR CODE HERE
def main():
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
M = int(data[1])
X = list(map(int, data[2:]))

# Calculate the initial total tour length
total_length = 0
for i in range(M - 1):
total_length += min(abs(X[i] - X[i + 1]), N - abs(X[i] - X[i + 1]))

# Calculate the contribution of each bridge
bridge_contribution = [0] * N
for i in range(M - 1):
a, b = X[i], X[i + 1]
if a > b:
a, b = b, a
bridge_contribution[a] += 1
bridge_contribution[b] -= 1

# Calculate the prefix sum to get the number of times each bridge is used
current_usage = 0
for i in range(N):
current_usage += bridge_contribution[i]
bridge_contribution[i] = current_usage

# Find the maximum usage of any bridge
max_usage = max(bridge_contribution)

# The minimum possible length is the total length minus the maximum usage
min_possible_length = total_length - max_usage

print(min_possible_length)

if __name__ == "__main__":
main()
```		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
Qwen2-72B-Instruct ```python
from collections import defaultdict

def solve():
N, M = map(int, input().split())
X = list(map(int, input().split()))

# Convert X to 0-indexed
X = [x - 1 for x in X]

# Find the cycle start and length
cycle_start = X[0]
cycle_length = 0
for i, x in enumerate(X):
if x == cycle_start:
cycle_length = i
break

# Adjust X to remove the cycle part
X = X[cycle_length:] + X[:cycle_length]

# Calculate the distance between consecutive elements in X
dist = [0] * M
for i in range(M - 1):
dist[i] = abs(X[i + 1] - X[i])
dist[-1] = abs(X[0] - X[-1])

# Calculate the prefix sum of dist
prefix_sum = [0] * (M + 1)
for i in range(M):
prefix_sum[i + 1] = prefix_sum[i] + dist[i]

# Calculate the minimum length of the tour
min_len = float('inf')
for i in range(M):
j = (i + 1) % M
if dist[i] == N - 1 or dist[j] == N - 1:
continue
len_with_bridge_closed = prefix_sum[M] - prefix_sum[i] - prefix_sum[j] + prefix_sum[min(i, j)] + prefix_sum[max(i, j) + 1] + 1
min_len = min(min_len, len_with_bridge_closed)

print(min_len)

solve()
```
This solution calculates the minimum possible length of the tour when the bridge to be closed is chosen optimally, considering the cycle structure of the islands and the distances between consecutive elements in the given sequence `X`.		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
DeepSeek-Coder-V2-Lite-Instruct ```python
# YOUR CODE HERE
def read_ints():
return list(map(int, input().split()))

N, M = read_ints()
X = read_ints()

# Create a dictionary to count the occurrences of each island
island_count = {}
for x in X:
island_count[x] = island_count.get(x, 0) + 1

# Create a list of islands sorted by their counts
sorted_islands = sorted(island_count.items(), key=lambda x: x[1])

# The minimum possible length of the tour is the sum of counts of all but the two most frequent islands
min_length = N - sum(count for island, count in sorted_islands[:-1])

print(min_length)
```		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
Meta-Llama-3.1-405B-Instruct-Turbo ```python
import sys

def solve():
n, m = map(int, sys.stdin.readline().split())
x = list(map(int, sys.stdin.readline().split()))

ans = 0
for i in range(m - 1):
ans += min(abs(x[i] - x[i + 1]), n - abs(x[i] - x[i + 1]))

mx = 0
for i in range(n):
l, r = i, i + 1
cnt = 0
for j in range(m - 1):
if (x[j] <= l and l < x[j + 1]) or (x[j] > l and l >= x[j + 1]):
cnt += 1
mx = max(mx, cnt)

print(ans + mx)

if __name__ == "__main__":
solve()
```		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
Meta-Llama-3.1-70B-Instruct-Turbo ```python
import sys

def main():
input = sys.stdin.readline
N, M = map(int, input().split())
X = list(map(int, input().split()))

X = [x - 1 for x in X]
X.append(X[0])

dist = [0] * M
for i in range(M):
dist[i] = (X[i + 1] - X[i]) % N

pref = [0] * (M + 1)
suff = [0] * (M + 1)
for i in range(M):
pref[i + 1] = pref[i] + dist[i]
suff[M - i - 1] = suff[M - i] + dist[M - i - 1]

ans = float('inf')
for i in range(M):
ans = min(ans, pref[i] + suff[i + 1] + min(dist[i], N - dist[i]))

print(ans)

if __name__ == "__main__":
main()
```		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
baichuan4 ```python
# YOUR CODE HERE
import sys

def read_input():
N, M = map(int, sys.stdin.readline().split())
X = list(map(int, sys.stdin.readline().split()))
return N, M, X

def find_bridge_to_close(N, M, X):
# Create a list to store the minimum tour length for each bridge closure
min_tour_lengths = [float('inf')] * N

# Iterate over each bridge to find the minimum tour length when that bridge is closed
for bridge in range(N):
# Create a dictionary to store the distance from each island to the next island in the tour
distances = {i: float('inf') for i in range(1, N + 1)}

# Set the initial distance to 0 for the first island in the tour
distances[X[0]] = 0

# Iterate over each island in the tour
for i in range(1, M):
# Create a new dictionary to store the updated distances
new_distances = {i: float('inf') for i in range(1, N + 1)}

# Iterate over each island
for island in distances:
# If the current island is not the next island in the tour, update its distance
if island != X[i]:
# Calculate the distance to the next island in the tour
distance = distances[island] + (1 if island != bridge else 2)

# Update the distance if it is smaller than the current distance
if distance < new_distances[X[i]]:
new_distances[X[i]] = distance

# Update the minimum tour length for the current bridge closure
min_tour_lengths[bridge] = new_distances[X[-1]]

# Return the minimum tour length over all bridge closures
return min(min_tour_lengths)

# Read the input
N, M, X = read_input()

# Find the bridge to close to minimize the tour length
min_tour_length = find_bridge_to_close(N, M, X)

# Print the minimum tour length
print(min_tour_length)
```		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
doubao ```python
N, M = map(int, input().split())
X = list(map(int, input().split()))

min_length = float('inf')
for bridge in range(1, N + 1):
visited = [False] * N
length = 0
current = X[0]
for i in range(1, M):
if current == X[i]:
continue
while current!= X[i]:
visited[current - 1] = True
if current < X[i]:
current += 1
else:
current -= 1
length += 1
if bridge == current and bridge + 1 <= N and not visited[bridge]:
length += 1
current += 1
elif bridge == current and bridge - 1 >= 1 and not visited[bridge - 2]:
length += 1
current -= 1
min_length = min(min_length, length)

print(min_length)
```		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE

import sys
import threading

def main():
import sys
import math
sys.setrecursionlimit(1 << 25)
N, M = map(int, sys.stdin.readline().split())
X = list(map(int, sys.stdin.readline().split()))
bridge_usage = [0] * (N + 2)
initial_total_cost = 0

for i in range(M -1):
u = X[i]
v = X[i+1]
delta = (v - u + N) % N
if delta == 0:
continue
elif delta <= N //2:
# Clockwise
initial_total_cost += delta
bridge_usage[u] += 1
bridge_usage[v] -=1
else:
# Counter-clockwise
delta = N - delta
initial_total_cost += delta
bridge_usage[v] +=1
bridge_usage[u] -=1

counts = [0] * (N + 1)
s = 0
min_usage = None
for p in range(1, N+1):
s += bridge_usage[p]
counts[p] = abs(s)

min_usage = min(counts[1:N+1])
total_cost = initial_total_cost + min_usage * (N - 2)
print(total_cost)


threading.Thread(target=main,).start()
```		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
kimi ```python
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
X = list(map(int, input().split()))
X = [x - 1 for x in X]
dist = [0] * N
for i in range(M - 1):
a = X[i]
b = X[i + 1]
if abs(a - b) == 1:
dist[(a + 1) % N] += 1
dist[(b + 1) % N] += 1
else:
dist[a] += 1
dist[(a + 1) % N] += 1
dist[b] += 1
dist[(b + 1) % N] += 1
ans = M - 1
for i in range(N):
if dist[i] == 2:
dist[i] = 1
if i == 0:
dist[-1] = 0
else:
dist[i - 1] = 0
else:
dist[i] = 0
if i == 0:
dist[-1] = 1
else:
dist[i - 1] = 1
ans = min(ans, M - 2 + sum(dist))
print(ans)
```		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
minimax ```python
# YOUR CODE HERE
from collections import defaultdict

def min_tour_length(N, M, X):
# Create a graph representation of the islands and bridges
graph = defaultdict(list)
for i in range(1, N):
graph[i].append(i + 1)
graph[i + 1].append(i)

# Function to calculate the length of the tour when a bridge is closed
def calculate_length(bridge):
length = 0
current = X[0]
for island in X[1:]:
if island == current:
continue
# Find the shortest path to the next island in the tour
next_island = min((n for n in graph[current] if n != bridge), key=lambda x: abs(x - island))
length += abs(next_island - island)
current = next_island
return length

# Calculate the minimum length of the tour for each bridge closure
min_length = float('inf')
for i in range(1, N + 1):
min_length = min(min_length, calculate_length(i))

return min_length

# Read the inputs from stdin
N, M = map(int,		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
wenxinyiyan ```python
from sys import stdin

def read_input():
n, m = map(int, stdin.readline().split())
x = list(map(int, stdin.readline().split()))
return n, m, x

def min_tour_length(n, m, x):
# Calculate prefix sums of island visits
prefix_sums = [0] * (n + 1)
for i in range(1, m):
diff = (x[i] - x[i - 1] + n) % n
prefix_sums[x[i - 1]] += diff
prefix_sums[x[i]] -= diff
for i in range(1, n):
prefix_sums[i] += prefix_sums[i - 1]

# Find the bridge closure that minimizes tour length
min_length = float('inf')
for i in range(1, n + 1):
# Calculate tour length if bridge i is closed
length = prefix_sums[i - 1] + (m - 1) * 2
if i < n:
length += (prefix_sums[n] - prefix_sums[i]) * 2
# Update minimum length if necessary
min_length = min(min_length, length)

# Adjust for the case where the tour starts and ends at the same island
if x[0] == x[-1]:
min_length -= 2

# The tour length needs to be at least m-1 (visiting m islands)
return max(m - 1, min_length)

# Read input and solve the problem
n, m, x = read_input()
result = min_tour_length(n, m, x)
print(result)
```

This Python program reads the input from standard input, solves the problem of finding the minimum tour length after optimally closing a bridge in the AtCoder Archipelago, and prints the result to standard output. The program uses prefix sums to efficiently calculate the tour lengths for each possible bridge closure and finds the minimum length among them.		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
zhipu ```python
def main():
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
M = int(data[1])
X = list(map(int, data[2:]))

# Adjust indices to be zero-based for easier calculations
X = [x - 1 for x in X]

# Calculate the initial tour length
initial_length = 0
for i in range(M - 1):
initial_length += (X[i + 1] - X[i]) % N

# Calculate the minimum possible length of the tour when one bridge is closed
min_length = float('inf')

# We need to consider the effect of closing each bridge
for i in range(N):
# Calculate the length of the tour if bridge i is closed
# Bridge i connects islands i and (i+1)%N
length_if_closed = initial_length

# Adjust the length for the segments affected by closing bridge i
for j in range(M - 1):
if (X[j] < X[j + 1] and X[j] <= i < X[j + 1]) or \
(X[j] > X[j + 1] and (i < X[j + 1] or i >= X[j])):
# If closing bridge i affects the path from X[j] to X[j+1]
length_if_closed += 1

# Special case for the last to first visit
if (X[M - 1] < X[0] and X[M - 1] <= i < X[0] + N) or \
(X[M - 1] > X[0] and (i < X[0] or i >= X[M - 1] + N)):
length_if_closed += 1

# Update the minimum length found
min_length = min(min_length, length_if_closed)

# Output the minimum length
print(min_length)

if __name__ == "__main__":
main()
```		 [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]
deepseek-v3 Error code: 400 - {'error': {'code': 'RequestTimeOut', 'param': None, 'message': 'Request timed out, please try again later.', 'type': 'RequestTimeOut'}, 'id': 'chatcmpl-89df2b86-6215-9e94-af9d-b83fedee9e31', 'request_id': '89df2b86-6215-9e94-af9d-b83fedee9e31'} [{"input": "3 3\n1 3 2\n", "output": "2\n", "testtype": "stdin"}, {"input": "4 5\n2 4 2 4 2\n", "output": "8\n", "testtype": "stdin"}, {"input": "163054 10\n62874 19143 77750 111403 29327 56303 6659 18896 64175 26369\n", "output": "390009\n", "testtype": "stdin"}]