Let \(v_i\) be the minimum length of the tour when bridge \(i\) is closed, and consider finding this \(v_i\) for all \(i=1,2,\dots,M\).

The tour can be decomposed into \(M-1\) movements: from island \(X_1\) to \(X_2\), from \(X_2\) to \(X_3\), …, and from \(X_{M-1}\) to \(X_M\). Since these movements are independent of each other, we can look at each movement one by one and add its contribution to each \(v_i\).

Now, consider moving from some island \(a\) to another island \(b\). There are two ways to move from island \(a\) to island \(b\) without crossing the same bridge multiple times: one is to go via \(a\rightarrow a+1\rightarrow a+2\rightarrow \dots \rightarrow b\), and the other is via \(a\rightarrow a-1\rightarrow a-2\rightarrow \dots \rightarrow b\). Let \(SZ\) denote the set of bridges crossed when going by the former method and \(T\) by the latter method. Here, \(S\) and \(T\) do not have common elements, and their union equals the entire set of bridges.

Depending on which set the closed bridge belongs to, there are two patterns:

• If the closed bridge belongs to \(S\): We use the bridge set \(T\) to move, so the length of the movement is \(|T|\).
• If the closed bridge belongs to \(T\): We use the bridge set \(S\) to move, so the length of the movement is \(|S|\).

Therefore, for each \(i\in S\), we add \(|T|\) to \(v_i\), and for each \(i\in T\), we add \(|S|\) to \(v_i\). As mentioned earlier, this operation needs to be done \(M-1\) times, so doing it naively will not be efficient. Instead, consider managing the difference array \(v'\) of \(v\) (where \(v'_i=v_i-v_{i-1}\)), then the operation “add \(x\) to \(v_l,v_{l+1},\dots,v_r\)” can be replaced with “add \(x\) to \(v'_{l}\) and subtract \(x\) from \(v'_{r+1}\)”, making each operation executable in \(O(1)\). After performing this for all \(M-1\) movements, we can obtain the desired array \(v\) by taking the cumulative sum of \(v'\). This technique is commonly known as the imos method among Japanese competitive programmers.

The overall time complexity is \(O(N)\). When implementing, be careful with cases where the addition spans across \(v_N,v_1\), like \(\dots,v_{N-1},v_N,v_1,v_2,\dots\).

Sample Implementation (C++) :

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    for (int &i: x) {
        cin >> i;
        --i;
    }
    vector<ll> v(n + 1);
    auto dist = [&](int from, int to) {
        if (from <= to) return to - from;
        else return to + n - from;
    };
    auto add = [&](int from, int to, int num) {
        if (from <= to) {
            v[from] += num;
            v[to] -= num;
        } else {
            v[from] += num;
            v[n] -= num;
            v[0] += num;
            v[to] -= num;
        }
    };
    for (int i = 0; i < m - 1; i++) {
        add(x[i], x[i + 1], dist(x[i + 1], x[i]));
        add(x[i + 1], x[i], dist(x[i], x[i + 1]));
    }
    ll ans = 1LL << 60;
    for (int i = 0; i < n; i++) {
        v[i + 1] += v[i];
        ans = min(ans, v[i]);
    }
    cout << ans << endl;
}