You are given an array(of integers) of length n. You are required to answer q queries. Queries can be of two types :- Update 0 idx val : set arr[idx] to val. Query 1 l r: find i,j such that l <= i < j <= r, such that arr[i]+arr[j] is maximized. return arr[i]+arr[j].
Input Format
A number n n1 n2 .. n number of elements A number q following q lines contains queries of format either of two 0 idx val 1 l r
Output Format
for each query of type 1 print a single integer in seperate line
Constraints
1. 1 <= n, q <= 10^5 2. 0 <= l < r < n 3. 0 <= idx < n 4. 1 <= arr[i], val <= 10^4.
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
8 2 6 1 5 4 10 10 9 5 1 0 4 0 0 10 1 0 4 1 0 7 1 3 4
Output
11 16 20 9