题目描述

给定一个长度为 $n$ 的序列 $a_1, a_2, . . . , a_n$，有 $m$ 次操作，每次操作为如下两种形式之一：

1. "1 l r”：从左到右遍历区间 $[l, r − 1]$ 中的每个 $i$，将 $a_i$ 赋值为 $max(a_i, a_{i+1})$。
2. “2 l r”：输出区间 $[l, r]$ 中所有前缀最大值的和。即对所有满足如下条件的 $a_i$ 求和：$l ≤ i ≤ r 且\max_{l≤j<i (a_j)} < a_i$。

保证初始时 $a_i$ 两两不同。

输入格式

第一行两个整数 $n, m$ 表示序列长度以及操作次数。

第二行 $n$ 个正整数 $a_{1,...,n}$ 表示给定的序列。

接下来 $m$ 行每行三个整数表示询问。

输出格式

对于每一个 $2$ 类询问输出一行表示答案。

样例

input1

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

output1

9
6

input2

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

output2

4
4

数据范围与提示

对于 7% 的数据，满足 $1 ≤ n, m ≤ 2000$。

对于另外 40% 的数据，满足对于所有 1 类操作，有 $l = 1, r = n$。

对于所有数据，满足$1 ≤ n, m ≤ 3 × 10^5，1 ≤ a_i ≤ 10^9, l < r$。