\(M\) 的处理很简单，具体证明看官解。
翻译自官方题解
提议者： Shinya Shiroshita，作者： Shinya Shiroshita，分析： Shinya Shiroshita。
首先，海鸥总数的一个明显下界是 \(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}})\) 是答案的一个下界。在下文中，我们通过给出构造来证明 \(M_{\mathrm{opt}}\) 是最优的。
首先，考虑某一天没有海鸥的情况。根据对称性，我们可以假设 \(b_n = 0\)。在这种情况下，从第 1 天开始，我们贪心地确定每只海鸥的停留时长，以便先到达的海鸥尽可能停留更长时间，如图所示。在下图中，每一列代表一天，每个字母代表一只海鸥的停留时长，每个数字代表当天观察到的海鸥总数。在这种情况下，\(S_{\mathrm{inc}} \geq D_{\mathrm{max}}\) 成立，因此 \(M_{\mathrm{opt}}\) 是最优的。
AAAAAAAAAA. ..BBBBBB... ...CC.DD... ----------- 11233233110接下来，考虑每天至少有一只海鸥的情况。令 \(D_{\mathrm{min}} = \min (b_1, \ldots , b_n)\)。全年停留的海鸥数量不一定是 \(D_{\mathrm{min}}\)，我们可以通过重叠海鸥的停留区间来减少这个数量，如图所示。
AAAAA....AAAAAA ..BBBBBBBBBB... --------------- 112221111222111现在从所有的 \(b_i\) 中减去 \(D_{\text{min}}\)，并考虑与第一种情况相同的贪心构造。在第一张图中，最终处于相同高度的海鸥（即到达时已停留海鸥数量相同的群体）形成了停留区间彼此不重叠的群体。对于每个这样的群体，通过循环移动其区间的端点，如下图所示，我们最多可以将全年停留的海鸥数量减少（群体大小 - 1）。
..AAA................ ..AAAAAAAAA.......... ..AAAAAAAAAAAAAAAAA.. .......BBBB.......... .......BBBBBBBBBBBB.. BBBBB..BBBBBBBBBBBBBB ...............CCCC.. -> CCCCC..........CCCCCC -> CCCCCCCCCCC....CCCCCC --------------------- --------------------- --------------------- 001110011110000111100 112221122221111222211 223332233332222333322如果在每个高度都应用此过程，我们总共可以将全年停留的海鸥数量恰好减少 \(S_{\text{inc}} - (D_{\text{max}} - D_{\text{min}})\)。如果 \(S_{\text{inc}} \geq D_{\text{max}} \iff S_{\text{inc}} - (D_{\text{max}} - D_{\text{min}}) \geq D_{\text{min}}\) 成立，那么通过将全年停留的海鸥数量恰好减少 \(D_{\text{min}}\) 次，我们可以得到一个总共有 \(S_{\text{inc}}\) 只海鸥的构造。另一方面，如果 \(S_{\text{inc}} < D_{\text{max}} \iff S_{\text{inc}} - (D_{\text{max}} - D_{\text{min}}) < D_{\text{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_{\text{opt}}\) 只海鸥的构造，因此 \(M_{\text{opt}}\) 是最优答案。
注：翻译为意译，不一定与原文相同，有错请指出。
根据官方题解的证明，我们其实能知道具体的构造了。
即所有值减去 \(D_{\text{min}}\)，之后贪心构造，循环位移 \(D_{\text{min}}\) 次即可。
:::info[推荐实现]{open}
选手 KudoShinichi 的代码，做了详细注释。
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>using namespace std;int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);int n;if (!(cin >> n)) return 0;// 读取输入 b[1...n]// 使用 1-based indexing 更方便vector<int> b(n + 1);int max_b = 0;for (int i = 1; i <= n; ++i) {cin >> b[i];max_b = max(max_b, b[i]); // 找到最大值}// in_count[i]: 第 i 天早上到达的海鸥数量// out_count[i]: 第 i 天傍晚离开的海鸥数量vector<int> in_count(n + 1, 0);vector<int> out_count(n + 1, 0);long long sum_starts = 0; // 总流入量（Flux）// 1. 计算循环差分（Cyclic Difference）// 比较第 1 天和第 n 天（循环边界）if (b[1] > b[n]) {in_count[1] += b[1] - b[n]; // 第1天需要增加sum_starts += b[1] - b[n]; // 累加总开始数} else {out_count[n] += b[n] - b[1]; // 第n天需要减少}// 比较相邻天for (int i = 2; i <= n; ++i) {if (b[i] > b[i - 1]) {in_count[i] += b[i] - b[i - 1]; // 需要新海鸥到达sum_starts += b[i] - b[i - 1]; // 累加总开始数} else {out_count[i - 1] += b[i - 1] - b[i]; // 需要海鸥离开}}// 2. 计算最小海鸥数量 Mlong long m = max((long long)max_b, sum_starts);cout << m << "\n";// 3. 构建时间表（仅当 M ≤ 200000 时）if (m <= 200000) {// 如果 M > sum_starts，需要添加全年停留的海鸥（额外部分）// 添加到第1天的到达和第n天的离开long long extra = m - sum_starts;in_count[1] += extra;out_count[n] += extra;// 计算 W：从去年跨到今年的海鸥数量（在第1天早上就在岛上）// 根据守恒原理：b[1] = W + In[1] => W = b[1] - In[1]// 注意：In[1] 已经包含额外部分int w = b[1] - in_count[1];// 使用双端队列（FIFO）代替向量（Stack）// 值 -1：跨年海鸥// 值 > 0：海鸥的开始日期deque<int> active_birds;// 存储跨年海鸥的结束日期vector<int> wrap_ends;// 初始化队列：放入 W 只跨年海鸥// 这些海鸥（值为-1）放在队列前端 -> 将首先被取出（FIFO）for (int k = 0; k < w; ++k) {active_birds.push_back(-1);}// 模拟每一天for (int i = 1; i <= n; ++i) {// 1. 海鸥到达：添加到队列尾部for (int k = 0; k < in_count[i]; ++k) {active_birds.push_back(i); // 记录开始日期}// 2. 海鸥离开：从队列头部取出for (int k = 0; k < out_count[i]; ++k) {int start_day = active_birds.front();active_birds.pop_front();if (start_day == -1) {// 跨年海鸥在 i 日结束wrap_ends.push_back(i);} else {// 普通海鸥：输出（开始日，结束日）cout << start_day << " " << i << "\n";}}}// 4. 配对剩余部分// 此时 active_birds 中剩余的数量应该等于 wrap_ends 的数量// 配对（队列中的开始日期，wrap_ends 中的结束日期）-> 形成跨年海鸥int wrap_idx = 0;while (!active_birds.empty()) {int start_day = active_birds.front();active_birds.pop_front();if (start_day == -1) {// 跨年海鸥（-1）仍在队列中 -> 从未被取出 -> 停留一整年cout << "1 " << n << "\n";} else {// 开始于 start_day 的海鸥，跨过新年，结束于 wrap_endsif (wrap_idx < wrap_ends.size()) {cout << start_day << " " << wrap_ends[wrap_idx++] << "\n";} else {// 安全回退（逻辑正确时不应该发生）cout << start_day << " 1\n";}}}}return 0;
}
:::
:::info[My Code]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n;
int b[N];
signed main(){cin>>n;for(int i=0;i<n;i++)cin>>b[i];int bmax=b[0];for(int i=1;i<n;i++)bmax=max(bmax,b[i]);int d=0;for(int i=0;i<n;i++)d+=max(0ll,b[(i+1)%n]-b[i]);int ans=max(d,bmax);cout<<ans<<'\n';if(ans>2e5) return 0;vector<pair<int,int> > ans_pair;int s=0;while(b[s]!=bmax) s++;while(bmax>d){ans_pair.push_back(make_pair(0,n - 1));bmax--;}int c=d-bmax;vector<int> xs;for(int k=0;k<n;k++) {int i=(s+k)%n;int v=b[(i+1)%n]-b[i];for(;v>0;v--)xs.push_back(i);for(;v<0;v++){if(c>0&&!xs.empty()&&xs.back()>=0){c--;ans_pair.push_back(make_pair((xs.back()+1)%n,i));xs.pop_back();}else{xs.push_back(-i-1);}}}vector<int> st;for(int i=0;i<xs.size();i++)if(xs[i]<0) st.push_back(-xs[i]-1);else{ans_pair.push_back({(xs[i] + 1) % n,st.back()});st.pop_back();}for(int i=0;i<ans_pair.size();i++)cout<<ans_pair[i].first+1<<' '<<ans_pair[i].second+1<<'\n';return 0;
}:::