시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB444100.000%

## 문제

Suppose you are given an array of n entries where each array entry is either 0 or 1. For any pair (ℓ, r) such that 1 ≤ ℓ ≤ r ≤ n, [a[ℓ], a[ℓ + 1], ..., a[r]] is a subarray of the array [a, a, ..., a[n]]. An alternating subarray [a[ℓ], a[ℓ + 1], ..., a[r]] of [a, a, ..., a[n]] if a[ℓ] ≠ a[ℓ + 1] ≠ ··· ≠ a[r]. 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, [1, 0, 1] is still an alterating subarray of [1, 1, 0, 1, 1].

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

• 1 ℓ r: for every i ∈ [ℓ, r], change a[i] into 1 − a[i].
• 2 ℓ r: report the total number of pairs (x, y) such that ℓ ≤ x ≤ y ≤ r and subarray [a[x], a[x + 1], ..., a[y]] 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 n and q, indicating the length of the given array and the number of operations. The second line contain n space separated numbers a, a, ..., a[n] representing the given array [a, a, ..., a[n]]. Then q lines follow, and the i-th of them contains 3 integers ti, ℓi, ri where the i-th operation is tii ri .

## 출력

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

## 제한

• 1 ≤ n ≤ 200000
• 1 ≤ q ≤ 200000
• a[i] ∈ {0, 1} for all i ∈ {1, 2, ..., n}.
• tj ∈ {1, 2} for all j ∈ {1, 2, ..., q}.
• 1 ≤ ℓj ≤ rj ≤ q for all j ∈ {1, 2, ..., q}.

## 예제 입력 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