#include<bits/stdc++.h>
using namespace std;
// 定义线段树节点结构体，存储四种状态的最大产奶量
struct SegTreeNode {
long long f00; // 左右端点都不选
long long f01; // 左端点不选，右端点选
long long f10; // 左端点选，右端点不选
long long f11; // 左右端点都选
SegTreeNode() : f00(0), f01(0), f10(0), f11(0) {}
};
vector<SegTreeNode> segTree; // 线段树数组
vector<int> M; // 存储每台挤奶机的产奶量
// 合并左右子节点的状态
SegTreeNode merge(const SegTreeNode& left, const SegTreeNode& right) {
SegTreeNode res;
// 计算f00：左区间右端点不选，右区间左端点不选
res.f00 = max(left.f00 + right.f00, left.f01 + right.f00);
res.f00 = max(res.f00, left.f00 + right.f10);
}
// 构建线段树
void build(int node, int start, int end) {
if (start == end) {
// 叶子节点初始化
segTree[node].f00 = 0; // 不选当前节点
segTree[node].f01 = -1e18; // 不可能的状态
segTree[node].f10 = -1e18; // 不可能的状态
segTree[node].f11 = M[start]; // 选当前节点
} else {
int mid = (start + end) / 2;
build(2 * node + 1, start, mid); // 构建左子树
build(2 * node + 2, mid + 1, end); // 构建右子树
segTree[node] = merge(segTree[2 * node + 1], segTree[2 * node + 2]); // 合并左右子树
}
}
// 更新线段树中某个节点的值
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
M[idx] = val; // 更新产奶量
segTree[node].f00 = 0;
segTree[node].f01 = -1e18;
segTree[node].f10 = -1e18;
segTree[node].f11 = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
update(2 * node + 1, start, mid, idx, val); // 更新左子树
} else {
update(2 * node + 2, mid + 1, end, idx, val); // 更新右子树
}
segTree[node] = merge(segTree[2 * node + 1], segTree[2 * node + 2]); // 合并更新后的子树
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
