|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||0||0||0||0.000%|
Mr. Oshiro wants to build a new hotel in Celeste Mountain Range. He needs you to find a good place him. First, Oshiro wants to build the hotel on a continuous segment without any valley in between, and the hotel should be as wide as possible. However, some places are too dangerous for the construction, so he will ask you this question several times: what is the maximum width of a constructible hotel in a certain segment of Celeste Mountain Range?
To clarify the problem statement, we define the following terms.
Mysterious phenomena often occur in Celeste Mountain Range. Sometimes the height of a certain area will change. But don’t worry, Mr. Oshiro will tell you the information just in time before he comes to you with more and more questions!
The first line contains one integer T, which is the number of test cases. In each test case, the first line contains one integer n, the length of Celeste Mountain Range in kilometers. The second line contains n integers denoting the initial heights. The third line contains one integer q which is the total number of queries and updates. Then q lines follow. Each of them is either in form “1 p d” or “2 ℓ r”. “1 p d” represents a mysterious phenomenon where p is the position and d is the amount of the height changed. That is, hp is updated with a new value hp + d. Note that d might be negative to indicate that a decrease in height. “2 ℓ r” represents the query from Oshiro. He wants to know the maximum width of the constructible hotel in the segment (ℓ, r) with height (hℓ, . . . , hr).
For each query, output one line containing the maximum width of a constructible hotel.
1 10 1 2 3 2 1 2 3 2 1 2 6 2 1 3 2 3 5 1 4 4 1 3 2 1 5 2 2 2 9
3 2 7