问题 C: Clamped Sequence II

For an integer sequence a1, a2, . . . , an and a positive integer d, the d-clamped value of the sequence is the maximum value of Pn−1 i=1 Pn j=i+1 |ai − aj |, where |x| is the absolute value of x, after appointing a range [l, r] satisfying 0 ≤ r − l ≤ d and clamping the sequence to the range [l, r]. More specifically, clamping the sequence to the range [l, r] makes each element ai :=    l, ai < l; ai , l ≤ ai ≤ r; r, ai > r. Both l and r are arbitrary real numbers decided by you under the given constraints. It can be shown that the maximum sum is always an integer. Now, given an integer sequence a1, a2, . . . , an and q queries, where each query is in one of the two following formats: • 1 x d denotes setting ax to d • 2 d denotes reporting the d-clamped value of the current sequence Please output the answer for each reporting queries.

The first line contains two integers n (2 ≤ n ≤ 105 ) and q (1 ≤ q ≤ 105 ), denoting the length of the given sequence and the number of queries. The second line contains n integers a1, a2, . . . , an (1 ≤ ai ≤ 106 ), denoting the given sequence. Each of the following q lines contains a query, which is in one of the two following formats: • 1 x d (1 ≤ x ≤ n, 1 ≤ d ≤ 106 ) denotes setting ax to d • 2 d (1 ≤ d ≤ 106 ) denotes reporting the d-clamped value of current sequence

For each reporting query, output one line containing a single integer, denoting the d-clamped value of the current sequence.

8 3
3 1 4 1 5 9 2 6
2 3
1 2 8
2 4

46
58