Sequence and Easy Queries

Interview

Time limit2sMemory limit1024 MB

Summary

With point updates on an array, count the maximal runs of equal adjacent values inside each queried subarray.

Level: Medium4 of 10
Topics: Array, Prefix sum
Solved: No attempts yet

Problem

A contiguous subarray $[a_l, a_{l+1}, \cdots, a_r]$ of a sequence is called a contiguous matching interval when all of its elements are equal. Such an interval $[l, r]$ is a contiguous matching interval of $a$ . An interval of $a$ is called an important contiguous matching interval if it is not fully contained in any other contiguous matching interval of $a$ .

You are given a sequence $A$ indexed from 1 and must answer $q$ queries.

1 i x: set $A_i$ to $x$ . ( $1 \le i, x \le n$ )
2 l r: let $B$ be the contiguous subsequence $[A_l, A_{l+1}, \cdots, A_r]$ . Print the number of distinct important contiguous matching intervals of $B$ . ( $1 \le l \le r \le n$ )

This is not a hard problem, is it? I hope it does not feel hard to you either.

Input

The first line contains two integers $n$ and $q$ , separated by a space. ( $1 \le n, q \le 2 \times 10^5$ )

The second line contains the elements $A_1, A_2, \cdots, A_n$ of the sequence, separated by spaces. ( $1 \le A_i \le n$ )

Each of the next $q$ lines contains one query. Each query is one of the types described in the problem.

The last query in every input is guaranteed to be of type 2.

Output

For each query of type 2, print the answer on its own line.

Examples1

Example 1

Input

10 9
1 1 1 2 2 1 1 4 4 4
2 1 10
2 2 6
2 2 5
1 2 7
2 1 10
2 2 6
2 7 8
1 7 4
2 7 8

Expected output