prieteni2

Prieteni2

== include(page="template/taskheader" task_id="prieteni2") ==

Poveste şi cerinţă...

Moş Crăciun a vrut să facă un experiment anul acesta, aşa că a adunat $n$ oameni şi i-a înşirat într-o linie. Se ştie că în această perioadă a anului se petrec *trei* tipuri de evenimente stranii.
 
* 1 i - omul *$i$* se împrieteneşte (ca prin minune) cu omul *$i + 1$*
* 2 i - omul *$i$* strică prietenia cu omul *$i + 1$* (un comportament neînţeles)
* 3 a b - Moş Crăciun se întreabă care este cel mai lung şir de prieteni din intervalul *$[a, b]$*
 
Moş Crăciun a încercat să îşi răspundă la întrebări, dar bătrâneţea îşi spune cuvântul. În final vă cere vouă să îl ajutaţi.

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $prieteni2.out$ ...

Fişierul de ieşire $prieteni2.out$ va conţine răspunsurile pentru evenimentele de tip *$3$*, fiecare pe câte o linie.

h2. Restricţii

* $... ≤ ... ≤ ...$

* pentru 40% din punctaj $1 ≤ n, q ≤ 3000$
* pentru alte 30% din punctaj $1 ≤ n, q ≤ 30000$
* pentru alte 30% din punctaj $1 ≤ n, q ≤ 200000$
* pentru evenimente de tip 1 se garantează că $1 ≤ i < n$ şi că i nu e prieten cu i + 1
* pentru evenimente de tip 2 se garantează că $1 ≤ i < n$ şi că i e prieten cu i + 1
* pentru evenimente de tip 3 se garantează că $1 ≤ a, b ≤ n$

h2. Exemplu

2
2
1

2
|

2|
| 3
4
1 2
3 1 3
2 2
3 2 3
| 2
1
|

h3. Explicaţie

h2. Explicaţie pentru exemplul 2

...

* 2 se împrieteneşte cu 3
* cel mai lung lanţ dintre 1 şi 3 este 2-3, de lungime 2
* 2 se supără cu 3
* cel mai lung lanţ dintre 2 şi 3 este de lungime 1 (doar 2, sau doar 3).

== include(page="template/taskfooter" task_id="prieteni2") ==