#216000. [TOPC 2021] Flip

Suppose you are given an array of entries where each array entry is either or . For any pair such that , is a subarray of the array . An alternating subarray of if . I.e., every entry in the subarray is different from its neighbors in the subarray. Since the definition of alternating subarrays only considers the entries in the subarrays, is still an altering subarray of .

In this problem, two types of operations will be applied to the given array.

• : for every , change into .
• : report the total number of pairs such that and subarray is an alternating subarray.

Please write a program to maintain the given array. Your program must report the numbers efficiently.

The first line contains two integers and , indicating the length of the given array and the number of operations. The second line contain space separated numbers representing the given array . Then lines follow, and the -th of them contains 3 integers where the -th operation is .

For each operation of the second type, output the reported number on one line.

样例输入 1

3 1
1 1 0
2 1 3

样例输出 1

4

样例输入 2

20 20
0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0
1 1 10
2 2 7
1 3 15
2 1 9
1 4 9
2 1 13
1 13 15
2 10 20
1 1 5
2 2 10
1 15 17
2 15 18
1 1 3
2 4 6
1 15 19
2 1 6
1 15 15
2 10 17
1 1 8
2 15 19

样例输出 2

16
16
21
14
12
6
4
9
10
8

• for all .
• for all .
• for all .