AT_codefestival_2015_final_j N個のバケツ

高桥君准备参加一个名为「桶节」的比赛。在这个节日中，有许多使用水桶进行的项目，高桥君选择了一个考验力量的项目，名为「$ N $ 个水桶」。 这个项目的规则如下： - 每队由 $ N $ 名成员组成，每名成员都有一个编号，从 $ 1 $ 到 $ N $。 - 他们按编号顺时针站成一个圈，这样，第 $ i $ 号和 $ i+1 $ 号成员，以及第 $ N $ 号和第 $ 1 $ 号成员就彼此相邻。 - 相邻的两名成员之间放置一个装有水的水桶，水桶的总数为 $ N $。队伍可以根据策略决定每个水桶中放多少水，但水量必须是整数。 - 每名队员需举起他两侧的水桶。两个水桶都需要两名邻近队员共同协作才能举起。如果所有 $ N $ 个水桶都被成功举起，则比赛成功，而水桶中水的总重量就是队伍的得分。 为了能得到最大的分数，高桥君需要决定水桶内的水量分配。为此，他先测量了每名队员的力量，已知第 $ i $ 号成员的力量为 $ S_i $。一个力量值为 $ p $ 的成员能够举起两侧的水桶，当且仅当这两个水桶内水量的平均值不超过 $ p $。具体来说，如果两桶水的量分别是 $ w $ 和 $ v $，那么应满足条件 $(w+v)/2 \le p$。 由于高桥君的队伍是临时组建的，成员可能会更换。比赛期间共有 $ Q $ 次成员变更。在第 $ i $ 次变更中，第 $ P_i $ 号成员被替换为力量为 $ X_i $ 的新成员。在每次变更之后，请计算出队伍可以达成的最大得分。

输入从标准输入中给出，格式如下： > $ N $ $ S_1 $ $ S_2 $ ... $ S_N $ $ Q $ $ P_1 $ $ X_1 $ $ P_2 $ $ X_2 $ : $ P_Q $ $ X_Q $ - 第一行包含一个整数 $ N\ (3 \le N \le 10^5) $，表示参赛人数。**在保证 100 分数据集的测试用例中，$ N $ 是偶数。** - 第二行包含 $ N $ 个整数，表示初始队员的力量。其中第 $ i $ 个整数 $ S_i\ (0 \le S_i \le 10^4) $ 表示第 $ i $ 号成员的力量。 - 第三行包含整数 $ Q\ (1 \le Q \le 10^5) $，表示成员变更的次数。 - 接下来的 $ Q $ 行中，每行包含两个整数 $ P_i\ (1 \le P_i \le N) $ 和 $ X_i\ (0 \le X_i \le 10^4) $，表示在第 $ i $ 次变更中，第 $ P_i $ 号成员被替换为新力量为 $ X_i $ 的成员。

输出包括 $ Q $ 行。每行表示一次成员变更后的最大得分。输出的每行末尾应有一个换行符。

### 额外得分 本题目有额外得分： - 如果你能准确计算 $ N $ 为奇数的数据集，你将获得额外的 1 分。 即使不拿额外分，也能通过 100 分的数据集，即算通过本题。 **本翻译由 AI 自动生成**