F1ow3rC0n

Taeyoung visited Sejong Lake Park during Humanities and Arts Exploration Week, took photos, and picked petals from a tree to use later. He later learned that picking petals from this tree was not allowed. So Taeyoung made a plan to glue the petals back onto the tree with glue.

Sejong Lake Park has $N$ trees in a row, and the type number of the flower on the $i$-th tree is $K\_i$. Taeyoung will glue petals onto the trees over $Q$ days as follows.

On the $i$-th day, one of the following two events occurs.

• Taeyoung uses glue to attach petals to trees $A\_i, A\_i+1, \cdots, B\_i$ in order.
• The type number of the flower on tree $A\_i$ changes to $B\_i$.

While examining the structure of the petals, Taeyoung realized that the glue type number must match the flower type number on the tree, and on the $i$-th day he decided to attach petals to glue as follows. Each day, Taeyoung starts out holding no glue.

• Taeyoung attaches petals to trees $A\_i$ through $B\_i$ in order. Note that the order of attaching petals is fixed.
• If Taeyoung is not holding glue, he can buy one bottle of glue of any type he wants.
• If Taeyoung is holding glue, he can throw that glue away.
• Taeyoung can attach a petal only when the type number of the flower on the tree he wants to attach it to equals the type number of the glue he is holding.

Taeyoung wonders, for each day he attaches petals, what is the minimum number of bottles of glue he must buy.

The first line gives the number of trees $N$ and the number of days $Q$ on which Taeyoung attaches petals, separated by a space.

The second line gives the flower type number of each tree, $K\_1, K\_2, \cdots, K\_N$, separated by spaces.

The $i$-th of the following $Q$ lines gives the type of event $T\_i$ and the values $A\_i$, $B\_i$ for the event, separated by spaces.

• If $T\_i = 1$, petals are attached to trees $A\_i$ through $B\_i$ in order.
• If $T\_i = 2$, the type number of the flower on tree $A\_i$ changes to $B\_i$.

For each day with $T\_i = 1$, print the minimum number of bottles of glue that must be bought, one per line.

• $1 \le N, Q \le 100\,000$
• $1 \le K\_i \le 100$ ($1 \le i \le N$)
• $1 \le T\_i \le 2$ ($1 \le i \le Q$)
• When $T\_i = 1$, $1 \le A\_i \le B\_i \le N$ ($1 \le i \le Q$)
• When $T\_i = 2$, $1 \le A\_i \le N$ ($1 \le i \le Q$)
• When $T\_i = 2$, $1 \le B\_i \le 100$ ($1 \le i \le Q$)
• There is at least one $i$ with $T\_i = 1$. ($1 \le i \le Q$)