Sorted Distances

 MoEngage has given you an array 

A$A$ consisting of N$N$ positive integers.

You should perform Q$Q$ queries of the following two types:

• 1$1$ i$i$ X$X$ : Set Ai$A_i$ to X$X$.
• 2$2$ L$L$ R$R$ : Find the minimum non-negative integer K$K$ such that the sequence [|AL−K|,|AL+1−K|,…,|AR−1−K|,|AR−K|]$[|A_L-K|,|A_{L+1}-K|,\dots ,|A_{R-1}-K|,|A_R-K|]$ is sorted in non-decreasing order. Print −1$-1$ if no such K$K$ exists.

For each query of type 2$2$, output the minimum non-negative integer K$K$ satisfying the constraint, or −1$-1$ if there isn't any.

Input Format

• The first line contains two integers N,Q$N,Q$.
• The second line contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.
• Then, the ith$i^{th}$ of the next Q$Q$ lines contains three integers describing the queries 1$1$ i$i$ X$X$ or 2$2$ L$L$ R$R$.

Output Format

For each query of type 2$2$, output the minimum integer K$K$ satisfying the constraint, or −1$-1$ if there isn't any in a new line.

Constraints

• 1≤N,Q≤2⋅105$1\le N,Q\le 2\cdot {10}^5$
• 0≤Ai,X≤109$0\le A_i,X\le {10}^9$
• 1≤L≤R≤N$1\le L\le R\le N$

Sample Input 1 

5 7
5 3 2 6 0
2 1 5
1 2 7
2 1 5
1 4 2
2 1 5
1 2 5
2 1 2

Sample Output 1 

4
-1
5
0

Explanation

• In the first query, selecting K=4$K=4$ makes the sequence 4$4$ satisfying this.

• In the second query, change A2=7$A_2=7$. After the second query, the array A$A$ becomes [5,7,2,6,0]$[5,7,2,6,0]$.

• In the third query, there exists no value of K$K$ satisfying the constraints.

• Tweet
• Share
• Share
• Share
• Share

Related Post