ABC 338

void solve() {
    ll n, m;
    cin >> n >> m;
    vll x(m);
    rep(i, m) {
        cin >> x[i];
        x[i]--;
    }

    vll cumsum(n * 2 + 1, 0);

    rep(i, m - 1) {
        ll mi = min(x[i], x[i + 1]);
        ll mx = max(x[i], x[i + 1]);

        ll dr = mx - mi;
        ll dl = n - dr;
        cumsum[mi] += dl;
        cumsum[mx] -= dl;
        cumsum[0] += dr;
        cumsum[mi] -= dr;
        cumsum[mx] += dr;
        cumsum[n] -= dr;
    }

    rep(i, n * 2) cumsum[i + 1] += cumsum[i];

    ll ans = INF;
    rep(i, n) chmin(ans, cumsum[i]);
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<pair<int, int>> ps;
    rep(i, N) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (a > b)
            swap(a, b);
        ps.emplace_back(a, b);
    }

    sort(all(ps), [](auto a, auto b) -> bool {
        return a.second < b.second;
    });

    auto op = [](ll a, ll b) -> ll { return a + b; };
    auto e = []() -> ll { return 0ll; };

    segtree<ll, op, e> seg(N * 2);
    rep(i, N) {
        seg.set(ps[i].first, 1);
    }

    bool ans = false;
    for (auto [a, b] : ps) {
        int sum = seg.prod(a + 1, b);
        if (sum > 0)
            ans = true;
        seg.set(a, -1);
        seg.set(b, 1);
    }
    yesno(ans);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vint P(N * 2);
    rep(i, N) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        P[a] = i;
        P[b] = i;
    }

    stack<int> st;
    rep(i, N * 2) {
        if (st.size() && st.top() == P[i]) {
            st.pop();
        } else {
            st.push(P[i]);
        }
    }

    yesno(st.size());
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;

    using P = pair<ll, ll>;
    vector<P> ps;
    rep(i, N) {
        ll a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        a--, b--;
        ps.emplace_back(a, b);
    }

    fenwick_tree<ll> fw(N * 2);
    for (auto [a, b] : ps) fw.add(a, 1);

    sort(all(ps), [](P a, P b) -> bool {
        return a.second < b.second;
    });

    int cross = 0;
    for (auto [a, b] : ps) {
        ll sum = fw.sum(a + 1, b);
        if (sum > 0) cross = 1;
        fw.add(a, -1);
    }
    yesno(cross);
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vint chords(N * 2, -1);
    rep(i, N) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        chords[u] = chords[v] = i;
    }

    vint st, appear(N);

    for (int x : chords) {
        if (appear[x]) {
            if (st.back() != x) {
                Yes();
                return;
            }
            st.pop_back();
        } else {
            st.pb(x);
            appear[x] = 1;
        }
    }
    No();
}