#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int64_t MAX_N = 1e5;
class SegmentTree {
private:
int32_t treeSize;
pair< pair< int64_t, int32_t >, int32_t > data[4 * MAX_N + 5];
void Build(int32_t nd, int32_t low, int32_t high, const vector< int64_t > &vals) {
if(low == high) {
data[nd] = { { vals[low - 1], -1 }, low };
return;
}
int64_t mid = (low + high) / 2;
Build(nd * 2, low, mid, vals);
Build(nd * 2 + 1, mid + 1, high, vals);
data[nd] = max(data[nd * 2], data[nd * 2 + 1]);
}
void Update(int32_t nd, int32_t low, int32_t high, int32_t qInd, int64_t qVal, int32_t qTime) {
if(low > qInd || high < qInd) {
return;
}
else if(low == qInd && high == qInd) {
data[nd] = { { qVal, qTime }, qInd };
return;
}
int32_t mid = (low + high) / 2;
Update(nd * 2, low, mid, qInd, qVal, qTime);
Update(nd * 2 + 1, mid + 1, high, qInd, qVal, qTime);
data[nd] = max(data[nd * 2], data[nd * 2 + 1]);
}
pair< pair< int64_t, int32_t >, int32_t > Query(int32_t nd, int32_t low, int32_t high, int32_t qLow, int32_t qHigh) {
if(low > qHigh || high < qLow) {
return { { -1, -1 }, -1 };
}
else if(low >= qLow && high <= qHigh) {
return data[nd];
}
int32_t mid = (low + high) / 2;
return max(Query(nd * 2, low, mid, qLow, qHigh), Query(nd * 2 + 1, mid + 1, high, qLow, qHigh));
}
public:
void Init(int32_t n) {
treeSize = n;
for(int32_t i = 1; i <= 4 * treeSize; i++) {
data[i] = { { -1, -1 }, -1 };
}
}
void Build(const vector< int64_t > &vals) {
Build(1, 1, treeSize, vals);
}
void Update(int32_t ind, int64_t val, int32_t t) {
Update(1, 1, treeSize, ind, val, t);
}
pair< pair< int64_t, int32_t >, int32_t > Query(int32_t low, int32_t high) {
return Query(1, 1, treeSize, low, high);
}
};
int32_t n;
int64_t distFromStart[MAX_N + 5], distToStart[MAX_N + 5];
priority_queue< pair< int64_t, int32_t > > furthestInTree[MAX_N + 5];
SegmentTree segTree;
pair< pair< int64_t, int32_t > , int32_t > FindFurthest(int64_t nd) {
pair< pair< int64_t, int32_t >, int32_t > aux1 = segTree.Query(1, nd - 1);
aux1.first.first += distToStart[nd];
pair< pair< int64_t, int32_t >, int32_t > aux2 = segTree.Query(nd, n);
aux2.first.first -= distFromStart[nd];
pair< pair< int64_t, int32_t >, int32_t > furthestPair = max(aux1, aux2);
return furthestPair;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int32_t i = 1; i <= n; i++) {
int32_t x;
cin >> x;
distFromStart[i + 1] = distFromStart[i] + (int64_t) x;
furthestInTree[i].push({ 0, -1 });
}
int64_t totalDist = distFromStart[n + 1];
for(int32_t i = 2; i <= n; i++) {
distToStart[i] = totalDist - distFromStart[i];
}
int32_t m;
cin >> m;
vector< int64_t > valsForSegTree(n);
for(int32_t i = 0; i < n; i++) {
valsForSegTree[i] = distFromStart[i + 1];
}
segTree.Init(n);
segTree.Build(valsForSegTree);
for(int32_t i = 0; i < m; i++) {
int32_t type;
cin >> type;
if(type == 1) {
int32_t x, w;
cin >> x >> w;
int32_t furthest = FindFurthest(x).second;
int64_t aux = furthestInTree[furthest].top().first + (int64_t) w;
furthestInTree[furthest].push({ aux, i });
int32_t t = furthestInTree[furthest].top().second;
segTree.Update(furthest, furthestInTree[furthest].top().first + distFromStart[furthest], t);
}
else if(type == 2) {
int32_t x, w;
cin >> x >> w;
furthestInTree[x].push({ (int64_t) w, i });
segTree.Update(x, furthestInTree[x].top().first + distFromStart[x], furthestInTree[x].top().second);
}
else if(type == 3) {
int32_t x;
cin >> x;
int32_t furthest = FindFurthest(x).second;
furthestInTree[furthest].pop();
int32_t aux = furthestInTree[furthest].top().second;
segTree.Update(furthest, furthestInTree[furthest].top().first + distFromStart[furthest], aux);
}
else {
int32_t x;
cin >> x;
pair< int64_t, int32_t > furthest = FindFurthest(x).first;
cout << furthest.first << endl;
}
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgZW5kbCAnXG4nCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQ2NF90IE1BWF9OID0gMWU1OwoKY2xhc3MgU2VnbWVudFRyZWUgewpwcml2YXRlOgoJaW50MzJfdCB0cmVlU2l6ZTsKCXBhaXI8IHBhaXI8IGludDY0X3QsIGludDMyX3QgPiwgaW50MzJfdCA+IGRhdGFbNCAqIE1BWF9OICsgNV07CgoJdm9pZCBCdWlsZChpbnQzMl90IG5kLCBpbnQzMl90IGxvdywgaW50MzJfdCBoaWdoLCBjb25zdCB2ZWN0b3I8IGludDY0X3QgPiAmdmFscykgewoJCWlmKGxvdyA9PSBoaWdoKSB7CgkJCWRhdGFbbmRdID0geyB7IHZhbHNbbG93IC0gMV0sIC0xIH0sIGxvdyB9OwoJCQlyZXR1cm47CgkJfQoKCQlpbnQ2NF90IG1pZCA9IChsb3cgKyBoaWdoKSAvIDI7CgkJQnVpbGQobmQgKiAyLCBsb3csIG1pZCwgdmFscyk7CgkJQnVpbGQobmQgKiAyICsgMSwgbWlkICsgMSwgaGlnaCwgdmFscyk7CgoJCWRhdGFbbmRdID0gbWF4KGRhdGFbbmQgKiAyXSwgZGF0YVtuZCAqIDIgKyAxXSk7Cgl9CgoJdm9pZCBVcGRhdGUoaW50MzJfdCBuZCwgaW50MzJfdCBsb3csIGludDMyX3QgaGlnaCwgaW50MzJfdCBxSW5kLCBpbnQ2NF90IHFWYWwsIGludDMyX3QgcVRpbWUpIHsKCQlpZihsb3cgPiBxSW5kIHx8IGhpZ2ggPCBxSW5kKSB7CgkJCXJldHVybjsKCQl9CgkJZWxzZSBpZihsb3cgPT0gcUluZCAmJiBoaWdoID09IHFJbmQpIHsKCQkJZGF0YVtuZF0gPSB7IHsgcVZhbCwgcVRpbWUgfSwgcUluZCB9OwoJCQlyZXR1cm47CgkJfQoKCQlpbnQzMl90IG1pZCA9IChsb3cgKyBoaWdoKSAvIDI7CgkJVXBkYXRlKG5kICogMiwgbG93LCBtaWQsIHFJbmQsIHFWYWwsIHFUaW1lKTsKCQlVcGRhdGUobmQgKiAyICsgMSwgbWlkICsgMSwgaGlnaCwgcUluZCwgcVZhbCwgcVRpbWUpOwoKCQlkYXRhW25kXSA9IG1heChkYXRhW25kICogMl0sIGRhdGFbbmQgKiAyICsgMV0pOwoJfQoKCXBhaXI8IHBhaXI8IGludDY0X3QsIGludDMyX3QgPiwgaW50MzJfdCA+IFF1ZXJ5KGludDMyX3QgbmQsIGludDMyX3QgbG93LCBpbnQzMl90IGhpZ2gsIGludDMyX3QgcUxvdywgaW50MzJfdCBxSGlnaCkgewoJCWlmKGxvdyA+IHFIaWdoIHx8IGhpZ2ggPCBxTG93KSB7CgkJCXJldHVybiB7IHsgLTEsIC0xIH0sIC0xIH07CgkJfQoJCWVsc2UgaWYobG93ID49IHFMb3cgJiYgaGlnaCA8PSBxSGlnaCkgewoJCQlyZXR1cm4gZGF0YVtuZF07CgkJfQoKCQlpbnQzMl90IG1pZCA9IChsb3cgKyBoaWdoKSAvIDI7CgkJcmV0dXJuIG1heChRdWVyeShuZCAqIDIsIGxvdywgbWlkLCBxTG93LCBxSGlnaCksIFF1ZXJ5KG5kICogMiArIDEsIG1pZCArIDEsIGhpZ2gsIHFMb3csIHFIaWdoKSk7Cgl9CgpwdWJsaWM6Cgl2b2lkIEluaXQoaW50MzJfdCBuKSB7CgkJdHJlZVNpemUgPSBuOwoKCQlmb3IoaW50MzJfdCBpID0gMTsgaSA8PSA0ICogdHJlZVNpemU7IGkrKykgewoJCQlkYXRhW2ldID0geyB7IC0xLCAtMSB9LCAtMSB9OwoJCX0KCX0KCgl2b2lkIEJ1aWxkKGNvbnN0IHZlY3RvcjwgaW50NjRfdCA+ICZ2YWxzKSB7CgkJQnVpbGQoMSwgMSwgdHJlZVNpemUsIHZhbHMpOwoJfQoKCXZvaWQgVXBkYXRlKGludDMyX3QgaW5kLCBpbnQ2NF90IHZhbCwgaW50MzJfdCB0KSB7CgkJVXBkYXRlKDEsIDEsIHRyZWVTaXplLCBpbmQsIHZhbCwgdCk7Cgl9CgoJcGFpcjwgcGFpcjwgaW50NjRfdCwgaW50MzJfdCA+LCBpbnQzMl90ID4gUXVlcnkoaW50MzJfdCBsb3csIGludDMyX3QgaGlnaCkgewoJCXJldHVybiBRdWVyeSgxLCAxLCB0cmVlU2l6ZSwgbG93LCBoaWdoKTsKCX0KfTsKCmludDMyX3QgbjsKaW50NjRfdCBkaXN0RnJvbVN0YXJ0W01BWF9OICsgNV0sIGRpc3RUb1N0YXJ0W01BWF9OICsgNV07CnByaW9yaXR5X3F1ZXVlPCBwYWlyPCBpbnQ2NF90LCBpbnQzMl90ID4gPiBmdXJ0aGVzdEluVHJlZVtNQVhfTiArIDVdOwpTZWdtZW50VHJlZSBzZWdUcmVlOwoKcGFpcjwgcGFpcjwgaW50NjRfdCwgaW50MzJfdCA+ICwgaW50MzJfdCA+IEZpbmRGdXJ0aGVzdChpbnQ2NF90IG5kKSB7CglwYWlyPCBwYWlyPCBpbnQ2NF90LCBpbnQzMl90ID4sIGludDMyX3QgPiBhdXgxID0gc2VnVHJlZS5RdWVyeSgxLCBuZCAtIDEpOwoJYXV4MS5maXJzdC5maXJzdCArPSBkaXN0VG9TdGFydFtuZF07CgoJcGFpcjwgcGFpcjwgaW50NjRfdCwgaW50MzJfdCA+LCBpbnQzMl90ID4gYXV4MiA9IHNlZ1RyZWUuUXVlcnkobmQsIG4pOwoJYXV4Mi5maXJzdC5maXJzdCAtPSBkaXN0RnJvbVN0YXJ0W25kXTsKCglwYWlyPCBwYWlyPCBpbnQ2NF90LCBpbnQzMl90ID4sIGludDMyX3QgPiBmdXJ0aGVzdFBhaXIgPSBtYXgoYXV4MSwgYXV4Mik7CglyZXR1cm4gZnVydGhlc3RQYWlyOwp9CgppbnQgbWFpbigpIHsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwoJY2luLnRpZShudWxscHRyKTsKCgljaW4gPj4gbjsKCglmb3IoaW50MzJfdCBpID0gMTsgaSA8PSBuOyBpKyspIHsKCQlpbnQzMl90IHg7CgkJY2luID4+IHg7CgoJCWRpc3RGcm9tU3RhcnRbaSArIDFdID0gZGlzdEZyb21TdGFydFtpXSArIChpbnQ2NF90KSB4OwoJCWZ1cnRoZXN0SW5UcmVlW2ldLnB1c2goeyAwLCAtMSB9KTsKCX0KCglpbnQ2NF90IHRvdGFsRGlzdCA9IGRpc3RGcm9tU3RhcnRbbiArIDFdOwoJZm9yKGludDMyX3QgaSA9IDI7IGkgPD0gbjsgaSsrKSB7CgkJZGlzdFRvU3RhcnRbaV0gPSB0b3RhbERpc3QgLSBkaXN0RnJvbVN0YXJ0W2ldOwoJfQoJCglpbnQzMl90IG07CgljaW4gPj4gbTsKCgl2ZWN0b3I8IGludDY0X3QgPiB2YWxzRm9yU2VnVHJlZShuKTsKCWZvcihpbnQzMl90IGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJdmFsc0ZvclNlZ1RyZWVbaV0gPSBkaXN0RnJvbVN0YXJ0W2kgKyAxXTsKCX0KCglzZWdUcmVlLkluaXQobik7CglzZWdUcmVlLkJ1aWxkKHZhbHNGb3JTZWdUcmVlKTsKCglmb3IoaW50MzJfdCBpID0gMDsgaSA8IG07IGkrKykgewoJCWludDMyX3QgdHlwZTsKCQljaW4gPj4gdHlwZTsKCgkJaWYodHlwZSA9PSAxKSB7CgkJCWludDMyX3QgeCwgdzsKCQkJY2luID4+IHggPj4gdzsKCQkJCgkJCWludDMyX3QgZnVydGhlc3QgPSBGaW5kRnVydGhlc3QoeCkuc2Vjb25kOwoJCQkKCQkJaW50NjRfdCBhdXggPSBmdXJ0aGVzdEluVHJlZVtmdXJ0aGVzdF0udG9wKCkuZmlyc3QgKyAoaW50NjRfdCkgdzsKCQkJZnVydGhlc3RJblRyZWVbZnVydGhlc3RdLnB1c2goeyBhdXgsIGkgfSk7CgkJCQoJCQlpbnQzMl90IHQgPSBmdXJ0aGVzdEluVHJlZVtmdXJ0aGVzdF0udG9wKCkuc2Vjb25kOwoJCQlzZWdUcmVlLlVwZGF0ZShmdXJ0aGVzdCwgZnVydGhlc3RJblRyZWVbZnVydGhlc3RdLnRvcCgpLmZpcnN0ICsgZGlzdEZyb21TdGFydFtmdXJ0aGVzdF0sIHQpOwoJCX0KCQllbHNlIGlmKHR5cGUgPT0gMikgewoJCQlpbnQzMl90IHgsIHc7CgkJCWNpbiA+PiB4ID4+IHc7CgkJCgkJCWZ1cnRoZXN0SW5UcmVlW3hdLnB1c2goeyAoaW50NjRfdCkgdywgaSB9KTsKCgkJCXNlZ1RyZWUuVXBkYXRlKHgsIGZ1cnRoZXN0SW5UcmVlW3hdLnRvcCgpLmZpcnN0ICsgZGlzdEZyb21TdGFydFt4XSwgZnVydGhlc3RJblRyZWVbeF0udG9wKCkuc2Vjb25kKTsKCQl9CgkJZWxzZSBpZih0eXBlID09IDMpIHsKCQkJaW50MzJfdCB4OwoJCQljaW4gPj4geDsKCQkJCgkJCWludDMyX3QgZnVydGhlc3QgPSBGaW5kRnVydGhlc3QoeCkuc2Vjb25kOwoJCQlmdXJ0aGVzdEluVHJlZVtmdXJ0aGVzdF0ucG9wKCk7CgkJCQoJCQlpbnQzMl90IGF1eCA9IGZ1cnRoZXN0SW5UcmVlW2Z1cnRoZXN0XS50b3AoKS5zZWNvbmQ7CgkJCXNlZ1RyZWUuVXBkYXRlKGZ1cnRoZXN0LCBmdXJ0aGVzdEluVHJlZVtmdXJ0aGVzdF0udG9wKCkuZmlyc3QgKyBkaXN0RnJvbVN0YXJ0W2Z1cnRoZXN0XSwgYXV4KTsKCQl9CgkJZWxzZSB7CgkJCWludDMyX3QgeDsKCQkJY2luID4+IHg7CgoJCQlwYWlyPCBpbnQ2NF90LCBpbnQzMl90ID4gZnVydGhlc3QgPSBGaW5kRnVydGhlc3QoeCkuZmlyc3Q7CgkJCWNvdXQgPDwgZnVydGhlc3QuZmlyc3QgPDwgZW5kbDsKCQl9Cgl9Cn0K