시간 제한메모리 제한제출정답맞힌 사람정답 비율
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[1], a[2], ..., a[n]]. An alternating subarray [a[ℓ], a[ℓ + 1], ..., a[r]] of [a[1], a[2], ..., 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[1], a[2], ..., a[n] representing the given array [a[1], a[2], ..., 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