Павле и Алекса се играју са сламкама. Оне су поређане у низ и њихове позиције су нумерисане бројевима од \(1\) до \(N\) слева надесно. Све сламке су различитих целобројних дужина од \(1\) до \(N\).

Отишли су код пророка Микија да им каже како ће се њихова игра одвијати. Он им је рекао да ће бити \(M\) дешавања за редом, и свако од њих ће бити у једном од два типа:

\(1\) \(l_i\) \(r_i\) - Алекса има прилику да промеша сламке (промени им редослед) на позицијама од \(l_i\) до \(r_i\) како год жели;

\(2\) \(x_i\) - Павле извлачи сламку на позицији \(x_i\) и одмах је врати на исто место.

Сви знају да, при извлачењу сламке, никако не желимо да извучемо најкраћу сламку. Пошто Павле нема слободу коју сламку ће извући (пророк Мики је увек у праву), а Алекса има слободу у мешању сламки, он жели да користи своје прилике за мешање да намести Павлу да што више пута извуче најкраћу сламку. Одредите колико је највише пута могуће да он то уради.

Описи функција

Потребно је да имплементирате функцију

• \(Slamke(N, A[\ldots], M, T[\ldots], X[\ldots], Y[\ldots])\)

где је \(N\) број који представља број сламки, низ \(A\), дужине \(N\) представља дужине сламки са лева на десно. Број \(M\) представља број дешавања, док низови \(T\), \(X\) и \(Y\) описују дешавања хронолошким редоследом. Уколико важи \(T[i] = 1\), значи да је \(i\)-то дешавање мешање сламки, па \(X[i]\) и \(Y[i]\) представљају леву и десну границу интервала који се меша. Уколико важи \(T[i] = 2\), значи да је \(i\)-то дешавање извлачење сламке, па \(X[i]\) представља индекс извучене сламке. У том случају важиће \(Y[i] = 0\). Сви низови су индексирани од 1. ## Пример

Нека су \(N=6\) и \(M = 4\), и нека су низови \(A=\{3, 1, 4, 6, 5, 2\}\), \(T=\{1, 2, 1, 2\}\), \(X=\{ 2, 5, 4, 5\}\) и \(Y=\{4, 0, 6, 0\}\): Након првог мешања није могуће наместити најкраћу сламку на позицију \(5\), али после другог јесте, па је резултат \(1\).

Нека су \(N=4\) и \(M = 4\), и нека су низови \(A=\{4, 3, 2, 1\}\), \(T=\{1, 2, 2, 2\}\), \(X=\{ 1, 1, 1, 3\}\) и \(Y=\{4, 0, 0, 0\}\): После првог мешања могуће је ставити сламку било где, али не истовремено и на позицију \(1\) и позицију \(3\). Од те две опције боља је опција \(1\), јер њу извлачи двапут, па је резултат \(2\).

Ограничења

• \(1 \leq N, M \leq 3\cdot10^5\)
• \(1 \leq A_i \leq N\)
• Сви елементи низа \(A_i\) различити.
• \(T_i \in \{1, 2\}\)
• Уколико \(T_i = 1\), важи \(1 \leq X_i \leq Y_i \leq N\).
• Уколико \(T_i = 2\), важи \(1 \leq X_i \leq N\), \(Y_i = 0\). ## Подзадаци Тест примери су подељени у \(6\) подзадатка:
• [14 поена]: Сва дешавања типа \(1\) се дешавају пре сваког дешавања типа \(2\).
• [9 поена]: \(M \leq 20\) и уколико \(T_i = 1\), важи \(Y_i - X_i = 1\).
• [13 поена]: Уколико \(T_i = 1\), важи \(Y_i - X_i = 1\).
• [15 поена]: \(N, M \leq 5000\).
• [13 поена]: \(M \leq 10000\).
• [36 поена]: Нема додатних ограничења ## Детаљи имплементације

Потребно је да пошаљете тачно један фајл izvlacenje_slamki.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

int Slamke(int N, int* A, int M, int* T, int* X, int* Y);

Вашим програмима је дозвољено да мењају садржај низова али не смеју да приступају ван граница датих низова.

Уз задатак, обезбеђен вам је “template” фајл code.cpp које можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• У првом реду број \(N\).
• У другом реду \(N\) бројева, низ \(A\).
• У трећем реду број \(M\).
• У наредних \(M\) редова по три броја у сваком реду, \(T_i\) \(X_i\) \(Y_i\).

Обратите пажњу да се број \(Y_i\) учитава и када је у питању дешавање другог типа. Тада је потребно да му вредност буде \(0\).

Затим овај програм позива вашу функцију и штампа резултат који је вратила ваша функција.