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].
# template begins
#####################################
from io import BytesIO, IOBase
import sys
import math
import os
import heapq
from collections import defaultdict, deque
from math import ceil
from bisect import bisect_left, bisect_right
from time import perf_counter


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")
def mint(): return map(int, input().split())
def mfloat(): return map(float, input().split())
def intin(): return int(input())


#####################################
# template ends
# Use the recursion snippet if heavy recursion is needed (depth>1000)
# If constraints are tight, use 1d arrays instead of 2d, like g[i*m+j] instead of g[i][j]

class Data:
    def __init__(self, value=None):
        self.first_value = self.last_value = value
        self.total = self.pref = self.suff = 1 if value is not None else 0
        self.size = 1 if value is not None else 0

    def __repr__(self):
        return f"Data: total = {self.total}, first_value = {self.first_value}, last_value = {self.last_value}"


class SegmentTree:
    def __init__(self, data, default=0, func=lambda a, b: a+b):
        self.n = len(data)
        self.default = default
        self.tree = [Data() for _ in range(2*self.n)]
        self.func = func
        for i in range(self.n, 2*self.n):
            self.tree[i] = Data(data[i-self.n])
        self.build()

    def combine(self, l, r):
        res = Data()
        if l.first_value is None:
            return r
        if r.first_value is None:
            return l
        res.size = l.size + r.size
        res.total = l.total + r.total

        if l.last_value <= r.first_value:
            res.total += l.suff * r.pref
        res.pref = l.pref
        if l.pref == l.size and l.last_value <= r.first_value:
            res.pref += r.pref
        res.suff = r.suff
        if r.suff == r.size and l.last_value <= r.first_value:
            res.suff += l.suff
        res.first_value = l.first_value
        res.last_value = r.last_value
        return res

    def build(self):
        """Build the tree"""
        for i in range(self.n-1, 0, -1):
            self.tree[i] = self.combine(self.tree[i << 1], self.tree[i << 1 | 1])

    def modify(self, index, value):
        """Set value at index"""
        index += self.n
        self.tree[index] = Data(value)
        while index > 1:
            self.tree[index >> 1] = self.combine(
                self.tree[index], self.tree[index ^ 1])
            index >>= 1

    def query(self, l, r):
        """Sum on interval [l, r)"""
        res = Data()
        l += self.n
        r += self.n
        while l < r:
            if l & 1:
                res = self.combine(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.combine(res, self.tree[r])
            l >>= 1
            r >>= 1
        return res.total

    def __getitem__(self, idx):
        return self.tree[idx + self.n]

    def __setitem__(self, index, value):
        self.modify(index, value)

    def __len__(self):
        return self.n

    def __repr__(self):
        return f"SegmentTree({self.tree})"


def solve():
    n, q = mint()
    *a, = mint()
    segTree = SegmentTree(a)
    for _ in range(q):
        type, x, y = mint()
        if type == 1:
            segTree[x-1] = y
        else:
            print(segTree.query(x-1, y))


def main():
    t = 1
    # t = int(input())
    for _ in range(t):
        solve()


if __name__ == "__main__":
    start_time = perf_counter()
    main()
    print(perf_counter()-start_time, file=sys.stderr)
