To convince Tianjiang not to remove the Abyss errors, Hefeng would like to better the world using the Abyss errors. She secretly left a blueprint of Chronosphere to her childhood friend Miming, and sent messages about the Abyss AI and the portal to her other friends like Guodong before she went to the Blue Planet with Yunyan again.

After that, since it's the last chance for Yunyan, he's too anxious to care much about Hefeng. So Hefeng toke on her own trip. Hefeng hoped to explore the possibilities of the Abyss power. So when Guodong arrived, they cooperated and made a great success in making games such as ONU and the Land of the Kernel. The game is so popular that even Yunyan had experienced it (of course with the purpose of finding better ways to use magic and fight with Tianjiang).

As expected, Miming successfully created another Chronosphere and used it. Both Hefeng and Yunyan kept their memory. First Hefeng escaped so that Yunyan couldn't take her to the portal. Then Yunyan failed to arrived the portal before Miming's team opened it. Knowing that Guodong would came later and knew how potential he was from the past memory, he decided to wait until Guodong's arrival and make use of Guodong. At the same time, Hefeng was trying to speed up the Abyss Cycle, since when it happens, the Abyss' power, including Yunyan's power, would be temporarily weaken. After Yunyan met Guodong and they went into the portal, Hefeng left a note in the Abyss and followed them into the portal later.

Passing through the portal again needs to use the magic flow skillfully.

The Blue Planet's magic flow has $n$ key point indexed from $1$ to $n$ , the $i$ key point need $a_i$ kinds of different magic elements to fix, and specially, every two adjacent key points should not have any same kind of magic elements. That is to say, for every $i\in[1,n]$ , let $b_i$ denotes the set of magic elements given to the $i$ key point, obviously the length of $b_i$ is $a_i$ . And for $i\in[1,n)$ , $b_i\cap b_{i+1}=\varnothing$ .

There're some pieces of sub-flow needs to fix, for every key point from $l$ to $r$ , you need to use total $k$ kinds of magic elements to allocate all the $b_i,i\in [l,r]$ , such that no adjacent key points in the sub-flow have any same element. You need to find the minimal $k$ to satisfy the requirement.

However, the magic flow is dynamic, so that $a_i$ changes with time. And there are $m$ operations in total, for every operation, either the $a_i$ changes forever, or you should calculate the $k$ with given $l,r$ .

The first line contains two integers $n,m(1\le n,m\le10^5)$ .

The second line contains $n$ integer, the i-th integer is $a_i(1\le a_i\le10^9)$ .

Then follow $m$ lines, each line has $3$ integers $c_j,l_j,r_j(1\le c_j\le2)$

• if $c_j=1$ , then change $a_{l_j}$ to $r_j$ forever. $(1\le l_j\le n,1\le r_j\le10^9)$
• if $c_j=2$ , then query the minimal $k$ of the sub-flow in $[l_j,r_j](1\le l_j\le r_j\le n)$

For every query, output one line with one integer denotes the minimal $k$ .

For the first query in flow piece $[3,3]$ , $a_3=2$ , one possible scheme is to allocate $b_3=(1,2)$ , and $k=2$ .

For the second query in flow piece $[1,2],a_1=2,a_2=3$ , one possible scheme is to allocate $b_1=(1,2),b_2=(3,4,5)$ and $k=5$ .

For the third query in flow piece $[1,3],a_1=2,a_2=3,a_3=3$ , one possible scheme is to allocate $b_1=(1,2),b_2=(3,4,5),b_3=(6,1,2)$ and $k=6$ .