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].

def naiveSolve():
    
    
    
    return



def solve():
    
    
    
    return

class SegmentTree(): # adapted from https://www.geeksforgeeks.org/segment-tree-efficient-implementation/
    def __init__(self,arr):
        def func(leftNode,rightNode): # for merging
            l1,r1,pre1,suf1,cnts1,mb1=leftNode
            l2,r2,pre2,suf2,cnts2,mb2=rightNode
            if mb1==-2: return rightNode
            if mb2==-2: return leftNode
            
            l3,r3=l1,r2
            cnts3=0
            if mb1==mb2==False: # both are increasing sequences
                if r1<=l2: # merge
                    pre3=suf3=pre1+pre2
                    mb3=False
                else: # split
                    pre3=pre1
                    suf3=suf2
                    mb3=True
            elif mb1==True and mb2==False:
                cnts3+=cnts1
                pre3=pre1
                mb3=True
                if r1<=l2:
                    suf3=suf1+pre2
                else:
                    cnts3+=(suf1*(suf1+1))//2
                    suf3=suf2
            elif mb1==False and mb2==True:
                cnts3+=cnts2
                suf3=suf2
                mb3=True
                if r1<=l2:
                    pre3=pre1+pre2
                else:
                    cnts3+=(pre2*(pre2+1))//2
                    pre3=pre1
            else:
                cnts3+=cnts1+cnts2
                pre3=pre1
                suf3=suf2
                mb3=True
                if r1<=l2:
                    aa=suf1+pre2
                    cnts3+=(aa*(aa+1))//2
                else:
                    cnts3+=(suf1*(suf1+1))//2+(suf2*(suf2+2))//2
            
            return (l3,r3,pre3,suf3,cnts3,mb3)
            
        self.f=func
        self.N=len(arr) 
        self.tree=[0 for _ in range(2*self.N)]
        self.initialRes=(-2,-2,-2,-2,-2,-2)
        for i in range(self.N):
            self.tree[self.N+i]=arr[i]
        for i in range(self.N-1,0,-1):
            self.tree[i]=self.f(self.tree[i<<1],self.tree[i<<1|1])
    def updateTreeNode(self,idx,value): #update value at arr[idx]
        self.tree[idx+self.N]=value
        idx+=self.N
        i=idx
        while i>1:
            self.tree[i>>1]=self.f(self.tree[i],self.tree[i^1])
            i>>=1
    def query(self,l,r): #get sum (or whatever function) on interval [l,r] inclusive
        r+=1
        left=self.initialRes
        right=self.initialRes
        l+=self.N
        r+=self.N
        while l<r:
            if l&1:
                # left=self.f(left,self.tree[l])
                left=self.f(self.tree[l],left)
                l+=1
            if r&1:
                r-=1
                # right=self.f(self.tree[r],right)
                right=self.f(right,self.tree[r])
            l>>=1
            r>>=1
        return self.f(left,right)

def main():
    
    n,q=readIntArr()
    arr=readIntArr()
    
    segData=[] # (leftValue,rightValue,preLen,sufLen,cnts,midBroken)
    for i,x in enumerate(arr):
        segData.append((x,x,1,1,0,False))
    
    st=SegmentTree(segData)
    
    allans=[]
    for _ in range(q):
        t,x,y=readIntArr()
        if t==1: # update
            x-=1
            st.updateTreeNode(x,(y,y,1,1,0,False))
        else: # query
            l,r=x-1,y-1
            data=st.query(l,r)
            # print(data)
            l,r,pre,suf,cnts,midBroken=data
            if midBroken==False:
                ans=(pre*(pre+1))//2
            else:
                ans=(pre*(pre+1))//2+(suf*(suf+1))//2+cnts
            allans.append(ans)
    # print(st.tree)
    multiLineArrayPrint(allans)
    
    return




import sys
input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
# input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
# def readFloatArr():
#     return [float(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
    dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(x):
    print('{}'.format(x))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
 
inf=float('inf')
# MOD=10**9+7
# MOD=998244353

from math import gcd,floor,ceil
# from math import floor,ceil # for Python2
 
for _abc in range(1):
    main()