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].
import java.util.*;
import java.io.*;
public class NDD {
    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        int n = fs.nextInt();
        int q = fs.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = fs.nextInt();
        Node.generateTree(arr);
        for(int i = 0; i < q; i++) {
            if(fs.nextInt() == 1)
                Node.update(fs.nextInt() - 1, fs.nextInt());
            else
                System.out.println(Node.query(fs.nextInt() - 1, fs.nextInt() - 1));
        }
    }
}

class Node {
    private static int[] arr;
    private static Node root;
    private Node lc, rc;
    private long val;
    private int first, last;
    private int l, r;
    public static Node generateTree(int[] arr) {
        Node.arr = arr;
        ArrayDeque<Node> dq = new ArrayDeque<Node>();
        for(int i = 0; i < arr.length; i++)
            dq.addLast(new Node(null, null, 0, i, i, -1, -1));
        while(dq.size() != 1) {
            Node lc = dq.pollFirst();
            if(dq.peek().r - dq.peek().l > lc.r - lc.l) {
                dq.addLast(lc);
                continue;
            }
            Node rc = dq.pollFirst();
            dq.addLast(merge(lc, rc));
        }
        root = dq.peek();
        return dq.poll();
    }
    private Node(Node lc, Node rc, long val, int l, int r, int first, int last) {
        this.lc = lc;
        this.rc = rc;
        this.val = val;
        this.l = l;
        this.r = r;
        this.first = first;
        this.last = last;
    }
    private static Node merge(Node lc, Node rc) {
        long val = lc.val + rc.val;
            int first = lc.first;
            int last = rc.last;
            if(arr[lc.r] > arr[rc.l]) {
                if(lc.last != -1)
                    val += chooseTwo(lc.r - lc.last + 1);
                if(rc.first != -1)
                    val += chooseTwo(rc.first - rc.l + 1);
                if(first == -1 || first > lc.r)
                    first = lc.r;
                if(last == -1 || last < rc.l)
                    last = rc.l;
            } else if(rc.first != -1 && lc.last != -1)
                val += chooseTwo(rc.first - lc.last + 1);
            if(first == -1 && rc.first != -1)
                first = rc.first;
            if(last == -1 && lc.last != -1)
                last = lc.last;
        return new Node(lc, rc, val, lc.l, rc.r, first, last);
    }
    private static long chooseTwo(long n) {
        return n * (n + 1) / 2;
    }
    public static void update(int idx, int v) {
        root = update(idx, v, root);
    }
    private static Node update(int idx, int v, Node curr) {
        if(curr.r - curr.l == 0) {
            arr[idx] = v;
            return curr;
        }
        if(curr.lc.l <= idx && curr.lc.r >= idx)
            curr.lc = update(idx, v, curr.lc);
        else
            curr.rc = update(idx, v, curr.rc);
        return merge(curr.lc, curr.rc);
    }
    public static long query(int l, int r) {
        Node ans = query(l, r, root);
        if(ans.first == -1)
            return chooseTwo(ans.r - ans.l + 1);
        return chooseTwo(ans.first - ans.l + 1) + chooseTwo(ans.r - ans.last + 1) + ans.val;
    }
    private static Node query(int l, int r, Node curr) {
        // System.out.println(curr);
        if(curr.l >= l && curr.r <= r)
            return curr;
        Node ln = null, rn = null;
        if(curr.lc.l <= r && curr.lc.r >= l)
            ln = query(l,r,curr.lc);
        if(curr.rc.l <= r && curr.rc.r >= l)
            rn = query(l,r,curr.rc);
        // System.out.println(ln + " " + rn);
        if(ln != null && rn != null)
            return merge(ln, rn);
        if(ln != null)
            return ln;
        return rn;
    }
    @Override
    public String toString() {
        return l + " " + r + " " + val + " " + first + " " + last + ",";
    }
}
class FastScanner {
    BufferedReader br;
    StringTokenizer tk;
    public FastScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
        tk = new StringTokenizer(" ");
    }
    public String next() throws IOException {
        if(!tk.hasMoreTokens())
            tk = new StringTokenizer(br.readLine());
        return tk.nextToken();
    }
    public int nextInt() throws IOException, NumberFormatException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException, NumberFormatException {
        return Long.parseLong(next());
    }
}