Qscmax

Cerință

Se dă un vector cu numere naturale. Avem mai multe operații de două feluri:

• Update: Elementul de pe o anumită poziție $p$ primește o valoare dată $x$.
• Query: Dați fiind doi indici $st$ și $dr$ să se determine lungimea subșirului crescător de lungime maximă pentru secvența care începe la poziția $st$ și se termină la poziția $dr$.

Date de intrare

Pe prima linie a fișierului qscmax.in se află numărul de elemente ale șirului dat, notat $n$.
Pe linia a doua se află $n$ numere, separate prin spațiu, reprezentând elementele șirului dat, în ordinea pozițiilor, numerotate de la $1$ la $n$.
Pe linia a treia se află numărul de operații, notat $m$. Pe fiecare din următoarele $m$ linii se află descrierea câte unei operații. Dacă avem update, linia va conține valorile $1$, $p$, $x$. Dacă avem query linia va conține valorile $2$, $st$, $dr$.

Date de ieșire

Fișierul de ieșire qscmax.out va conține, pentru fiecare interogare rezultatul, în ordinea aparițiilor din fișierul de intrare. Valorile se scriu pe o linie, separate prin spațiu.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$;
• În orice moment, valorile șirului sunt $0$, $1$, $2$ sau $3$;
• $1 \leq m \leq 100 \ 000$;
• Avem cel puțin o operație “query”;
• $1 \leq p \leq n$;
• $1 \leq st \leq dr \leq n$.

Exemplu

qscmax.in

9
0 1 3 0 1 2 1 2 0
3
2 1 9
1 3 0
2 1 3

qscmax.out

5 2

Explicație

La prima interogare se cere lungimea subșirului crescător din tot șirul dat. Aceasta este $5$.
La a doua interogare se cere lungimea subșirului crescător pentru elementele de pe poziții de la $1$ la $3$. Aceasta este $2$ (elementul de pe poziția $3$ a devenit între timp $0$).