Prieteni2

prieteni2

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

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.

Poveste şi cerinţă...

h2. Date de intrare

h2. Date de ieşire

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

Fişierul de ieşire $prieteni2.out$ 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|
| 3
4
1 2
3 1 3
2 2
3 2 3
| 2
1
|

2
|

h2. Explicaţie pentru exemplul 2

h3. Explicaţie

* 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") ==