In the Master Chef competition, two talented chefs, Chưng and Quýt, are competing. They are both masters of balancing flavors, but today, they are solving a special challenge using numbers instead of ingredients.

A Taste of the Peak in an array is defined as an element that is greater than both its previous and next elements in array.

Chef Chưng task is to count how many peaks appear in certain parts of the array, while Chef Quýt can modify the array to influence the results for Chưng.

You are given an array 'nums' some queries to help Chef Chưng. You need to process the queries of two types:

• ~1, l, r~: Chef Chưng must determine the number of Taste of the Peak elements in the subarray nums[l..r].
• ~2, p, v~: Chef Quýt changes the element at nums[p] to v,

Input

The first line contains two integers ~n~ and ~q~ with ~(1 ≤ n ≤ 10^5, 1 ≤≤ 10^5)~ being the number of elements in the array and the number of queries

The second line contains n numbers in the array nums with ~(0 ≤ nums[i] ≤ 10^6)~.

The following Q lines each belong to one of the following two categories:

• ~1 l r~: Chef Chưng must determine the number of Taste of the Peak elements in the subarray nums[l..r] with ~(1 ≤ l ≤ r ≤ n)~.
• ~2 p v~: Chef Quýt changes the element at nums[p] to ~v~ with ~(1 ≤ p ≤ n, 0 ≤ v ≤ 10^6)~,

Output

The answer of each type query if it is type 1.

Sample Input 1

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

Sample Ouput 1

0
1

Note:

• First we assign nums[3] = 4
• With the query of segment [1, 3] we do not get any valid value
• With the second query of segment [1, 5] we get a satisfying value nums[3]