You are given an array \(A\) consisting of \(N\) elements \(A_1, A_2, A_3,\ ..., A_N\). You must process \(N\) queries and there are two types of queries:

\(1\ L\ R\): Replace \(L^{th}\) element by \(R\), that is, \(A_L=R\).
\(2\ L\ R\): You are required to print the minimum number of operations to make all elements equal in subarrays \(A_L,A_{L+1},\ ..., A_R\)_.

You can perform the following operation in order to make elements equal:

Select any index \(L\) and replace \(A_L\) with \(A_L+1\) or \(A_L+2\).

Note: You do not have to modify the original array in a query of type 2.

Input format

The first line contains two space-separated integers \(N\) and \(Q\).
The second line contains space-separated integers \(A_1, A_2, A_3,\ ..., A_N\).
Each of next \(Q\) lines contains three integers type \(L\), \(R\) denoting the type of query and its parameters.

Output format

Print a single integer for every query of the second type.

Constraints

\(1 \leq N \leq 500000\)
\(1 \leq Q \leq 500000\)
\(1 \leq A_i \leq 1e9 \forall i \in [1,N]\)

The types of queries are either 1 or 2.

If the type is 1:

\(1 \leq L \leq N\)
\(1 \leq R \leq 1e9\)

If the type is 2:

\(1 \leq L \leq R \leq N\)