#include<bits/stdc++.h>
using namespace std;
int a[100010],n,ans=0,i;
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    for(int i=n;i>=1;i--){
        if((a[i]+ans&1)==0)ans=(a[i]+ans)>>1;
        else ans=(a[i]+ans>>1)+1;
    }
    cout<<ans;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010 * 31, M = 100010;

int n, m;
int s[M];
int son[N][2], cnt[N], idx;

void insert(int x, int v)
{
    int p = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
        cnt[p] += v;
    }
}

int query(int x)
{
    int res = 0, p = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int u = x >> i & 1;
        if (cnt[son[p][!u]]) p = son[p][!u], res = res * 2 + 1;
        else p = son[p][u], res = res * 2;
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        s[i] = s[i - 1] ^ x;
    }

    int res = 0;
    insert(s[0], 1);

    for (int i = 1; i <= n; i ++ )
    {
        if (i > m) insert(s[i - m - 1], -1);
        res = max(res, query(s[i]));
        insert(s[i], 1);
    }

    printf("%d\n", res);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=10,INF=0x3f3f3f3f;
int n,m;
int w[N],s[N];
int f[N][N][M],g[N][N][M];
int get_mod(int x)
{
    return (x%10+10)%10;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        w[i+n]=w[i];
    }
    for(int i=1;i<=n*2;i++)s[i]=s[i-1]+w[i];
    memset(f,0x3f,sizeof(f));
    memset(g,-0x3f,sizeof(g));
    for(int len=1;len<=n;len++)
        for (int l=1;l+len-1<=n*2;l++){
            int r=l+len-1;
            f[l][r][1]=g[l][r][1]=get_mod(s[r]-s[l-1]);
            for(int k=2;k<=m;k++)
                for(int j=l+k-2;j<r;j++){
                    f[l][r][k]=min(f[l][r][k],f[l][j][k-1]*get_mod(s[r]-s[j]));
                    g[l][r][k]=max(g[l][r][k],g[l][j][k-1]*get_mod(s[r]-s[j]));
                }
        }
    int maxv=-INF,minv=INF;
    for(int i=1;i<=n;i++){
        maxv=max(maxv,g[i][i+n-1][m]);
        minv=min(minv,f[i][i+n-1][m]);
    }
    cout<<minv<<endl;
    cout<<maxv;
}

#include<bits/stdc++.h>
using namespace std;

int main() 
{
    int n,m,i,x,t,c=0,ans=0;
    cin>>t;
    while(t--){
        cin>>n>>m;
        c=0,ans=0;
        for(int i=1;i<=n;i++){
            cin>>x;
            if(c+x>m){
                ans++;
                c=0;    
            }
            c+=x;
        }
        if(c!=0)ans++;
        cout<<ans<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int n,x;
string st;
int main() 
{
    cin>>n;
    while(n--){
        cin>>x>>st;
        string str;
        for(int i=0;i<x-1;i++){
            if(st[i]>st[i+1]){
                str+=st.substr(i+1); 
                break;
            }
            str+=st[i];
        }
        cout<<str<<'\n';
    }
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

int n;
int w[N];

int dfs(int l, int r)
{
    bool flag = true;
    for (int i = l; i < r; i ++ )
        if (w[i] > w[i + 1])
            flag = false;
    if (flag) return r - l + 1;
    int mid = l + r >> 1;
    return max(dfs(l, mid), dfs(mid + 1, r));
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        for (int i = 0; i < n; i ++ ) cin >> w[i];
        cout << dfs(0, n - 1) << endl;
    }
    return 0;
}

class Solution {
public:
    string greatestLetter(string s) {
        unordered_set<char> S;
        for (auto c: s) S.insert(c);
        for (char i = 'z'; i >= 'a'; i -- ) {
            if (S.count(i) && S.count(i - 32)) {
                return string(1, i - 32);
            }
        }

        return "";
    }
};

class Solution {
public:
    int minimumNumbers(int num, int k) {
        if (!num) return 0;
        for (int x = 1; x <= 10; x ++ )
            if (x * k % 10 == num % 10 && x * k <= num)
                return x;
        return -1;
    }
};

要一个特判

#include<bits/stdc++.h>
using namespace std;
long long n,a[100001],i;
int main()
{
    set<pair<long long,int>>a;
    a.insert({2000000000,-1});
    a.insert({-2000000000,-1});
    cin>>n;
    if(n==2){
        cout<<"2000000000 1";
        return 0;
    }
    for(i=1;i<=n;i++){
        long long x;
        cin>>x;
        if(i>1){
            auto right=a.lower_bound({x,-1});
            auto left=a.upper_bound({x,-1});
            left--;
            long long r=(long long)right->first-x;
            long long l=(long long)x-left->first;
            if(l<=r)cout<<l<<' '<<left->second<<endl;
            else cout<<r<<' '<<right->second<<endl;
        }
        a.insert({x,i});
    }
}

class Solution {
public:
    vector<int> printMatrix(vector<vector<int>>& matrix) {
        vector<int> res;
        if (matrix.empty()) return res;
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<bool>> st(n, vector<bool>(m, false));
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        int x = 0, y = 0, d = 1;
        for (int k = 0; k < n * m; k ++ )
        {
            res.push_back(matrix[x][y]);
            st[x][y] = true;

            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b])
            {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        return res;
    }
};