\(v_i=\)（橋 \(i\) を封鎖したときのツアーの長さの最小値）とおいて、この \(v_i\) を全ての \(i=1,2,\dots,M\) について求めることを考えます。

ツアーは、島 \(X_1\rightarrow X_2,X_2\rightarrow X_3,\dots,X_{M-1}\rightarrow X_M\) という \(M-1\) 個の移動に分解されます。これらの移動は互いに独立なので、順番に \(1\) つずつ見ていって、それぞれの移動の寄与分を各 \(v_i\) に足していけばよいです。

今、ある島 \(a\) からある島 \(b\) への移動について考えているとします。島 \(a\) から島 \(b\) まで（同じ橋を複数回渡ることなく）移動する方法は、\(a\rightarrow a+1\rightarrow a+2\rightarrow \dots \rightarrow b\) と行く方法と \(a\rightarrow a-1\rightarrow a-2\rightarrow \dots \rightarrow b\) と行く方法の \(2\) 通りがあります。前者で行ったときに通る橋の集合を \(S\)、後者で行ったときに通る橋の集合を \(T\) とおきます。ここで、\(S\) と \(T\) は共通する要素を持たず、和集合は橋全体の集合と一致します。

封鎖する橋がどちらの集合に属するかによって、以下の \(2\) パターンが考えられます。

• 封鎖する橋が \(S\) に属する場合: 橋集合 \(T\) を使って移動するので、移動の長さは \(|T|\) になる。（集合 \(X\) の要素数を \(|X|\) と表記しています）
• 封鎖する橋が \(T\) に属する場合: 橋集合 \(S\) を使って移動するので、移動の長さは \(|S|\) になる。

よって、各 \(i\in S\) に対して \(v_i\) に \(|T|\) を加算し、各 \(i\in T\) に対して \(v_i\) に \(|S|\) を加算すればよいです。前述の通りこの操作は全部で \(M-1\) 回行う必要があるので、愚直にやっていては間に合いません。そこで、\(v\) の代わりにその差分配列 \(v'\)（\(v'_i=v_i-v_{i-1}\) と定義される配列）を管理することを考えると、「\(v_l,v_{l+1},\dots,v_r\) に \(x\) を加算する」という操作は「\(v'_{l}\) に \(x\) を加算し、\(v'_{r+1}\) に \(-x\) を加算する」という操作に置き換わるので、各操作 \(O(1)\) で実行可能になります。\(M-1\) 個の移動全てについてこれを行ったあと、\(v'\) の累積和を取ることで目的の配列 \(v\) が得られます。この手法は俗に imos 法と呼ばれます。

全体の計算量は \(O(N)\) です。実装の際は、加算する対象が \(\dots,v_{N-1},v_N,v_1,v_2,\dots\) のように \(v_N,v_1\) を跨いでいる場合の処理に気をつけてください。

実装例 (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;
}