# GSS6 - Can you answer these queries VI

## 题意翻译

## 题目大意 给出一个由$N$个整数组成的序列$A$，你需要应用$M$个操作： * I p x 在$~p~$处插入插入一个元素$~x~$ * D p 删除$~p~$处的一个元素 * R p x 修改$~p~$处元素的值为$~x~$ * Q l r 查询一个区间$\left[l,r\right]$的最大子段和 ## 输入格式 第一行一个数$N$，表示序列的长度 第二行$N$个数，表示初始序列$A$ 第三行一个数$M$，表示操作的次数 接下来的$M$行，每行一个操作，格式见题目描述 ## 输出格式 输出若干行，每行一个整数，表示查询区间的最大子段和 感谢@Anoxiacxy 提供的翻译

## 题目描述

Given a sequence A of N _(N <= 100000)_ integers, you have to apply Q _(Q <= 100000)_ operations: Insert, delete, replace an element, find the maximum contiguous(non empty) sum in a given interval.

## 输入输出格式

### 输入格式

The first line of the input contains an integer N. The following line contains N integers, representing the starting sequence A1..AN, _(|Ai| <= 10000)_. The third line contains an integer Q. The next Q lines contains the operations in following form: **I x y**: insert element y at position x _(between x - 1 and x)_. **D x** : delete the element at position x. **R x y**: replace element at position x with y. **Q x y**: print max{Ai + Ai+1 + .. + Aj | x <= i <= j <= y}. All given positions are valid, and given values are between -10000 and +10000. The sequence will never be empty.

### 输出格式

For each **"Q"** operation, print an integer(one per line) as described above.

## 输入输出样例

### 输入样例 #1

5
3 -4 3 -1 6
10
I 6 2
Q 3 5
R 5 -4
Q 3 5
D 2
Q 1 5
I 2 -10
Q 1 6
R 2 -1
Q 1 6


### 输出样例 #1

8
3
6
3
5