Background

无

Description

在一片神秘的山脉中，有 N 座山峰，每座山峰的高度为Ai。山脉的守护者需要时刻关注这些山峰的变化，因为山峰的高度会随着时间改变。守护者的任务是在 M 次询问内快速回答以下问题： 1. 修改：某座山峰的高度发生变化：将第 k 座山峰的高度改为 h。 2. 查询：在区间[l,r]内，有多少座山峰是“守护峰”。守护峰的定义是：它比左右两边的两座山峰都要高。 注意，区间[l,r]的两端的山峰不被定义为守护峰 你需要帮助守护者高效地完成这些任务。

Format

Input

第一行包含两个整数 N 和 M(1<=N,M<=$10^5$)。 第二行包含 N 个整数，表示初始山峰高度数组 A(0<=Ai<=$10^9$)。 接下来 M 行，每行表示一个操作： 修改操作格式为1 k h (1<=k<=N,0<=h<=$10^9$)。 查询操作格式为2 l r (1<=l<r<=N,若r-l+1<3,输出0）。

Output

对于每个查询操作，输出一行，包含一个整数表示答案。

Samples

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

2
1
1

Limitation

1s, 256MB for each test case.