(M) の処理については公式解説を参照されたい。

まず，海鸥の全总数的明显な下界は (b_i) の最大值であり，(D_{\mathrm{max}} = \max(b_1, \ldots, b_n)) である。これは，いずれかの日に观察到的海鸥数が海鸥の総数をを超えることはできないためである。同様に，增加分の合計も

[S_{\mathrm{inc}} = \sum_{i = 1, \ldots, n} \max(b_i - b_{i - 1}, 0) \quad (\text{where } b_0 = b_n)]

海鸥总数的另一个下界である。实际に，(b_i > b_{i-1}) ならば，第 (i) 日には少なくとも (b_i - b_{i-1}) 羽の海鸥が島に到達する。 따라서，(M_{\mathrm{opt}} = \max(D_{\mathrm{max}}, S_{\mathrm{inc}})) は答えの下界となる。以下では，この値が最適であることを具体的な構成で示す。

まず，某 дня海鸥がいないケースを考える。対称性により，(b_n = 0) と仮定してよい。この場合，第1日から始めて，各海鸥の滞在時間を貪欲に决定し，先に到達した海鸽ほど長く滞在するようにする。下の図では，各列は各日を，各文字は各海鸥の滞在期間，各数字はその日に观察到的海鸥数を示す。この場合，(S_{\mathrm{inc}} \geq D_{\mathrm{max}}) が成立し，(M_{\mathrm{opt}}) が最適であることがわかる。

AAAAAAAAAA.
..BBBBBB...
...CC.DD...
-----------
11233233110

次に，每日に少なくとも1羽の海鸥がいるケース考える。(D_{\mathrm{min}} = \min(b_1, \ldots, b_n)) とする。一年中滞在する海鸥の数が必ずしも (D_{\mathrm{min}}) である必要はなく，海鸥の滞在区間を重複させることで減らすことができる（如下图所示）。

AAAAA....AAAAAA
..BBBBBBBBBB...
---------------
112221111222111

ここで，全ての (b_i) から (D_{\mathrm{min}}) を引き，第一のケース同様の貪欲構成を考える。最初の図で，最終的に同じ高さにいる海鸥（即ち，到着時に既に滞在していた海鸥数が同じ群体）は，滞在期間が互いに重ならない群体を形成する。各群体について，以下のように区間の端点を循環移動させることで，群体サイズ-1 だけ一年中滞在する海鸥数を減らすことができる。

..AAA................    ..AAAAAAAAA..........    ..AAAAAAAAAAAAAAAAA..
.......BBBB..........    .......BBBBBBBBBBBB..    BBBBB..BBBBBBBBBBBBBB
...............CCCC.. -> CCCCC..........CCCCCC -> CCCCCCCCCCC....CCCCCC
---------------------    ---------------------    ---------------------
001110011110000111100    112221122221111222211    223332233332222333322

各高さでこのプロセスを適用すると，一年中最小限滞在する海鸥数をちょうど (S_{\mathrm{inc}} - (D_{\mathrm{max}} - D_{\mathrm{min}})) だけ減らすことができる。(S_{\mathrm{inc}} \geq D_{\mathrm{max}} \iff S_{\mathrm{inc}} - (D_{\mathrm{max}} - D_{\mathrm{min}}) \geq D_{\mathrm{min}}) が成立するなら，一年中最少滞在する海鸥数をちょうど (D_{\mathrm{min}}) 回減らすことで，全てで (S_{\mathrm{inc}}) 羽の海鸥を持つ構成を得られる。一方，(S_{\mathrm{inc}} < D_{\mathrm{max}} \iff S_{\mathrm{inc}} - (D_{\mathrm{max}} - D_{\mathrm{min}}) < D_{\mathrm{min}}) が成立するなら，

[D_{\text{min}} - (S_{\text{inc}} - (D_{\text{max}} - D_{\text{min}})) = D_{\text{max}} - S_{\text{inc}} ]

羽的一年中最少滞在する海鸥が必要となり，海鸥の総数は

[S_{\text{inc}} + (D_{\text{max}} - S_{\text{inc}}) = D_{\text{max}}.]

いずれの場合も，ちょうど (M_{\mathrm{opt}}) 羽の海鸥を持つ構成が得られます。因此，(M_{\mathrm{opt}}) が最优答案である。

根据上の证明，具体的な构成方法は全てもとの値から (D_{\mathrm{min}}) を引き，之后貪欲に构成し，循环位移を (D_{\mathrm{min}}) 回行う就可以了。

実装例（C++）：

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> obs(n + 1);
    int max_obs = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> obs[i];
        max_obs = max(max_obs, obs[i]);
    }

    // arrival[i]: 第i天早上到达的海鸥数
    // departure[i]: 第i天傍晚离开的海鸥数
    vector<int> arrival(n + 1, 0);
    vector<int> departure(n + 1, 0);
    long long total_arrivals = 0;

    // 循环差分の计算
    if (obs[1] > obs[n]) {
        arrival[1] += obs[1] - obs[n];
        total_arrivals += obs[1] - obs[n];
    } else {
        departure[n] += obs[n] - obs[1];
    }

    for (int i = 2; i <= n; ++i) {
        if (obs[i] > obs[i - 1]) {
            arrival[i] += obs[i] - obs[i - 1];
            total_arrivals += obs[i] - obs[i - 1];
        } else {
            departure[i - 1] += obs[i - 1] - obs[i];
        }
    }

    long long min_seagulls = max((long long)max_obs, total_arrivals);
    cout << min_seagulls << "\n";

    // スケジュール構築（最小海鸥数が20万以下の場合）
    if (min_seagulls <= 200000) {
        long long additional = min_seagulls - total_arrivals;
        arrival[1] += additional;
        departure[n] += additional;

        // 年跨ぎの海鸥数（第一天早上すでに岛にいている）
        int carry_over = obs[1] - arrival[1];

        deque<int> active_queue;
        vector<int> carry_ends;

        // 年跨ぎの海鸥を队列に投入
        for (int i = 0; i < carry_over; ++i) {
            active_queue.push_back(-1);
        }

        // 各日のシミュレーション
        for (int day = 1; day <= n; ++day) {
            // 新しい海鸥が到着
            for (int i = 0; i < arrival[day]; ++i) {
                active_queue.push_back(day);
            }

            // 海鸥が离开
            for (int i = 0; i < departure[day]; ++i) {
                int start_day = active_queue.front();
                active_queue.pop_front();

                if (start_day == -1) {
                    carry_ends.push_back(day);
                } else {
                    cout << start_day << " " << day << "\n";
                }
            }
        }

        // 残りの海鸥をペアリング
        int idx = 0;
        while (!active_queue.empty()) {
            int start_day = active_queue.front();
            active_queue.pop_front();

            if (start_day == -1) {
                cout << "1 " << n << "\n";
            } else {
                if (idx < (int)carry_ends.size()) {
                    cout << start_day << " " << carry_ends[idx++] << "\n";
                } else {
                    cout << start_day << " 1\n";
                }
            }
        }
    }

    return 0;
}

別の実装例（C++）：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n; ++i) cin >> b[i];

    int bmax = *max_element(b.begin(), b.end());

    int delta = 0;
    for (int i = 0; i < n; ++i)
        delta += max(0, b[(i + 1) % n] - b[i]);

    int answer = max(delta, bmax);
    cout << answer << '\n';

    if (answer > 200000) return 0;

    vector<pair<int, int>> result;
    int c = delta - bmax;

    // bmax > delta の场合，全年滞在する海鸥を追加
    while (bmax > delta) {
        result.emplace_back(0, n - 1);
        --bmax;
    }

    vector<int> stack_data;
    int start_idx = 0;
    while (b[start_idx] != bmax) ++start_idx;

    // 貪欲な构建
    for (int k = 0; k < n; ++k) {
        int i = (start_idx + k) % n;
        int diff = b[(i + 1) % n] - b[i];

        // 正の差分：海鸥到达
        for (; diff > 0; --diff)
            stack_data.push_back(i);

        // 负の差分：海鸥离开
        for (; diff < 0; ++diff) {
            if (c > 0 && !stack_data.empty() && stack_data.back() >= 0) {
                --c;
                result.emplace_back((stack_data.back() + 1) % n, i);
                stack_data.pop_back();
            } else {
                stack_data.push_back(-i - 1);
            }
        }
    }

    // 年跨ぎの处理
    vector<int> carry_stack;
    for (int x : stack_data)
        if (x < 0) carry_stack.push_back(-x - 1);
        else {
            result.emplace_back((x + 1) % n, carry_stack.back());
            carry_stack.pop_back();
        }

    for (auto &p : result)
        cout << p.first + 1 << ' ' << p.second + 1 << '\n';

    return 0;
}