现在有 $n$ 只青鸹，每只青鸹有一个毒瘤系数，他们排成了一个序列。

你可以重复以下操作，直到序列中只剩下一只青鸹的时候停止，每次操作可以自选进行 $1$ 还是 $2$ 操作，并且自选进行操作的位置：

1. 选择一只在序列端点位置的青鸹，将这只青鸹杀死。

2. 选择一只在序列非端点位置的青鸹（假设在 $i$ 位置），将这只青鸹（ $i$ 位置）杀死，将这只青鸹旁边的两只青鸹（$i-1$ 与 $i+1$ 位置）合体（即合体为一只青鸹，其毒瘤系数为两只青鸹的毒瘤系数加起来的和），放在 $i$ 位置上。

每次操作结束后，如果一个位置没有青鸹，则其后面的青鸹会自动补位，也就是说不会有空位。

你想让最后剩下的青鸹的毒瘤系数最高，请输出这个最高的毒瘤系数，并且输出最少操作次数。

$n\le 10^6$

---

显然两个数要对答案产生贡献，二者之间的数的个数必为奇数，如果是偶数，就不能仅删除中间的部分。

手模后发现，设对答案产生贡献的数为 $a_{p_1},a_{p_2},\dots ,a_{p_k}$，$p_1\equiv p_2\equiv \cdots \equiv p_n(\mathrm{mod}2)$。

所以最优策略是在奇数或偶数位置选全部正数，然后确定了选的数后，把相邻两个数之间的连续段删去即可，发现中间的最小操作次数就是连续段长度除以 $2$，两边的段单独求。

特判序列全部都是负数的情况。

时间复杂度 $O(n)$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dis(x) (x>1?(x+1>>1):0)
constexpr ll INF=1e18;
const int N=1e6+1;
int n,cnt1,cnt2;
ll ans1,ans2,a[N];
struct node
{ll x,i;
}b1[N],b2[N];
int main()
{freopen("friends.in","r",stdin);freopen("friends.out","w",stdout);cin.tie(0)->sync_with_stdio(0);int fl=0;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];if(i&1) b1[++cnt1]={a[i],i};else b2[++cnt2]={a[i],i};if(a[i]>0) fl=1;}if(!fl){ll maxn=-INF,maxi;for(int i=1;i<=n;i++){if(maxn<a[i]){maxn=a[i];maxi=dis(i)+dis(n-i+1);}else if(maxn==a[i]) maxi=min(maxi,1ll*dis(i)+dis(n-i+1));}cout<<maxn<<"\n"<<maxi;return 0;}ll maxi=-INF,mini=INF,sum=0;for(int i=cnt1;i>=1;i--){if(b1[i].x<=0) continue;sum+=b1[i].x;maxi=max(maxi,b1[i].i);mini=min(mini,b1[i].i);}ans1=sum,ans2=(maxi-mini)/2+dis(mini)+dis(n-maxi+1);sum=0,maxi=-INF,mini=INF;for(int i=cnt2;i>=1;i--){if(b2[i].x<=0) continue;sum+=b2[i].x;maxi=max(maxi,b2[i].i);mini=min(mini,b2[i].i);}if(ans1<sum) ans1=sum,ans2=(maxi-mini)/2+dis(mini)+dis(n-maxi+1);else if(ans1==sum) ans2=min(ans2,(maxi-mini)/2ll+dis(mini)+dis(n-maxi+1));cout<<ans1<<"\n"<<ans2;
}