Alice has recently received an array a_1, a_2, ..., a_n for her birthday! She is very proud of her array, and when she showed her friend Bob the array, he was very happy with her present too!

However, soon Bob became curious, and as any sane friend would do, asked Alice to perform q operations of two types on her array:

  * 1 x y: update the element a_x to y (set a_x = y). 
  * 2 l r: calculate how many non-decreasing subarrays exist within the subarray [a_l, a_{l+1}, ..., a_r]. More formally, count the number of pairs of integers (p,q) such that l ≤ p ≤ q ≤ r and a_p ≤ a_{p+1} ≤ ... ≤ a_{q-1} ≤ a_q. 



Help Alice answer Bob's queries!

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 2 ⋅ 10^5) — the size of the array, and the number of queries, respectively.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the elements of Alice's array.

The next q lines consist of three integers each. The first integer of the i-th line is t_i, the operation being performed on the i-th step (t_i = 1 or t_i = 2).

If t_i = 1, the next two integers are x_i and y_i (1 ≤ x_i ≤ n; 1 ≤ y_i ≤ 10^9), updating the element at position x_i to y_i (setting a_{x_i} = y_i).

If t_i = 2, the next two integers are l_i and r_i (1 ≤ l_i ≤ r_i ≤ n), the two indices Bob asks Alice about for the i-th query.

It's guaranteed that there is at least one operation of the second type.

Output

For each query of type 2, print a single integer, the answer to the query.

Example

Input


5 6
3 1 4 1 5
2 2 5
2 1 3
1 4 4
2 2 5
1 2 6
2 2 5


Output


6
4
10
7

Note

For the first query, l = 2 and r = 5, and the non-decreasing subarrays [p,q] are [2,2], [3,3], [4,4], [5,5], [2,3] and [4,5].
/*
stream Butter!
eggyHide eggyVengeance
I need U
xiao rerun when
 */
import static java.lang.Math.*;
import java.util.*;
import java.io.*;
import java.math.*;

public class x1567E
{
    static int N;
    public static void main(String hi[]) throws Exception
    {
        segtree = new Node[690420];
        BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(infile.readLine());
        N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        st = new StringTokenizer(infile.readLine());
        for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        if(N == 1)
        {
            //trivial case
            while(Q-->0)
            {
                st = new StringTokenizer(infile.readLine());
                int T = Integer.parseInt(st.nextToken());
                if(T == 2)
                    sb.append("1\n");
            }
            System.out.print(sb);
            return;
        }
        N--;
        for(int i=0; i < N; i++)
        {
            Node lol = new Node(0, 0, 0);
            if(arr[i+1] >= arr[i])
                lol = new Node(1,1, 1);
            update(i, lol);
        }
        while(Q-->0)
        {
            st = new StringTokenizer(infile.readLine());
            int type = Integer.parseInt(st.nextToken());
            if(type == 1)
            {
                int dex = Integer.parseInt(st.nextToken())-1;
                int val = Integer.parseInt(st.nextToken());
                arr[dex] = val;
                //figure out how difference array changes
                if(dex < arr.length-1)
                {
                    Node lol = new Node(0L, 0, 0);
                    if(arr[dex+1] >= arr[dex])
                        lol = new Node(1L, 1, 1);
                    update(dex, lol);
                }
                if(dex > 0)
                {
                    Node lol = new Node(0L, 0, 0);
                    if(arr[dex] >= arr[dex-1])
                        lol = new Node(1L, 1, 1);
                    update(dex-1, lol);
                }
            }
            else
            {
                int left = Integer.parseInt(st.nextToken())-1;
                int right = Integer.parseInt(st.nextToken())-1;
                if(left == right)
                    sb.append("1\n");
                else
                {
                    Node result = query(left, right-1);
                    sb.append(result.cnt+(right-left+1)+"\n");
                }
            }
        }
        System.out.print(sb);
    }
    static Node[] segtree;
    public static void update(int loc, Node x)
    {
        updateHelper(1, 0, N-1, loc, x);
    }
    public static void updateHelper(int id, int L, int R, int dex, Node val)
    {
        if(L == dex && R == dex)
        {
            segtree[id] = val;
            return;
        }
        if(R < dex || L > dex)
            return;
        int mid = (L+R)>>1;
        updateHelper(id<<1, L, mid, dex, val);
        updateHelper((id<<1)+1, mid+1, R, dex, val);
        segtree[id] = comb(segtree[id<<1], segtree[(id<<1)+1], mid-L+1, R-mid);
    }
    public static Node query(int left, int right)
    {
        return queryHelper(1, 0, N-1, left, right);
    }
    public static Node queryHelper(int id, int L, int R, int left, int right)
    {
        if(R < left || right < L)
            return null;
        if(left <= L && R <= right)
            return segtree[id];
        int mid = (L+R)>>1;
        return comb(queryHelper(id<<1, L, mid, left, right), queryHelper((id<<1)+1, mid+1, R, left, right), mid-L+1, R-mid);
    }
    public static Node comb(Node a, Node b, int lenA, int lenB)
    {
        if(a == null)
            return b;
        if(b == null)
            return a;
        long tot = a.cnt+b.cnt+(long)a.suffix*b.prefix;
        int pref = a.prefix;
        if(a.prefix == lenA)
            pref += b.prefix;
        int suff = b.suffix;
        if(b.suffix == lenB)
            suff += a.suffix;
        return new Node(tot, pref, suff);
    }
}
/*
difference subarray --> no negative number
segment tree on difference array
node info:
-# of subarrays with no negative number
-longest prefix length with no negative number
-longest suffix length with no negative number
 */
class Node
{
    public long cnt;
    public int prefix;
    public int suffix;

    public Node(long c, int a, int b)
    {
        cnt = c;
        prefix = a;
        suffix = b;
    }
}