호텔

Mr. Oshiro는 Celeste 산맥에 새 호텔을 지으려고 한다. 그는 호텔을 지을 좋은 자리를 찾아 달라고 부탁한다. 먼저 Oshiro는 중간에 골짜기가 없는 하나의 연속한 구간 위에 호텔을 짓고 싶어 하며, 호텔은 가능한 한 넓어야 한다. 그런데 일부 지역은 공사에 너무 위험하기 때문에, 그는 여러 번 다음과 같은 질문을 한다. Celeste 산맥의 어떤 구간에서 지을 수 있는 호텔의 최대 너비는 얼마인가?

문제를 명확히 하기 위해 다음과 같은 용어를 정의한다.

• Celeste 산맥은 길이가 n킬로미터이다.
• 지형(지표면의 모양)은 평균 높이를 미터 단위로 나타낸 정수열 h0, . . . , hn−1로 표현된다. hi는 Celeste 산맥의 i번째 킬로미터에서 (i + 1)번째 킬로미터까지 지역의 평균 높이이다.
• 모든 질의는 Celeste 산맥의 연속한 구간이며, 이에 대응하는 높이 수열을 가진다.
• 골짜기는 양옆보다 낮은 지점이다. 이 문제에서 hi < min(hi−1, hi+1)이고 0 < i < n−1일 때 i번째 킬로미터에서 (i+1)번째 킬로미터까지 지역을 골짜기라고 부른다. 첫 번째 킬로미터 앞 지역과 (n − 2)번째 킬로미터 뒤 지역은 h−1과 hn이 정의되지 않으므로 골짜기로 보지 않는다.
• 연속한 구간은 양 끝을 제외하고 골짜기를 포함하지 않으면 단봉 구간이다. 예를 들어 질의 구간의 높이가 (1, 2, 3, 4, 3, 4, 5)라면, 높이가 (1, 2, 3, 4, 3)인 구간과 (3, 4, 5)인 구간은 단봉 구간이지만, 높이가 (3, 4, 3, 4)인 구간은 아니다.
• Mr. Oshiro는 단봉 구간에만 호텔을 짓는다. 따라서 높이가 (1, 2, 3, 4, 3, 4, 5)인 앞의 질의에 대한 답은 5이다.

Celeste 산맥에서는 신비로운 현상이 자주 일어난다. 때때로 어떤 지역의 높이가 변한다. 하지만 걱정하지 말자. Mr. Oshiro는 더 많은 질문을 하러 오기 전에 그 정보를 알려 줄 것이다!

첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스에서 첫 번째 줄에는 Celeste 산맥의 길이를 킬로미터 단위로 나타낸 정수 n이 주어진다. 두 번째 줄에는 초기 높이를 나타내는 n개의 정수가 주어진다. 세 번째 줄에는 질의와 갱신의 총 개수인 정수 q가 주어진다. 그다음 q개의 줄이 주어진다. 각 줄은 "1 p d" 또는 "2 ℓ r" 형태이다. "1 p d"는 신비로운 현상을 나타내며, p는 위치이고 d는 높이 변화량이다. 즉, hp가 새로운 값 hp + d로 갱신된다. d가 음수일 수 있으며 이는 높이가 감소함을 나타낸다. "2 ℓ r"은 Oshiro의 질의를 나타낸다. 그는 높이가 (hℓ, . . . , hr)인 구간 (ℓ, r)에서 지을 수 있는 호텔의 최대 너비를 알고 싶어 한다.

각 질의마다 지을 수 있는 호텔의 최대 너비를 한 줄에 하나씩 출력한다.

• 1 ≤ T ≤ 10
• 1 ≤ n ≤ 105
• 1 ≤ q ≤ 105
• p, ℓ, r ∈ {0, 1, . . . , n − 1}
• 높이는 항상 [1, 109] 범위이다.
• 어떤 변화 이후에도 모든 0 < i < n에 대해 hi−1 ̸= hi임이 보장된다.