Problem description

Ach lemury, lemury, lemury, znowu oszukują i znęcają się nad biednymi pingwinami; tym razem robią to, poruszając się po koronach drzew, deklasując przy tym pingwiny w grze polowej, ale jak to na świecie bywa, każda bajka musi się kończyć happy-endem, a pingwiny muszą ostatecznie górować nad ssakami.

– Nie jest tajemnicą, że lemury mnie nic nie obchodzą – groźnie powiedział Skipper.

– Nawzajem, gburze we fraku! – odburknął Julian.

W celu zdeklasowania lemurów w grze polowej nasze nieloty poczuły chęć latania. I tak wyposażywszy się w jetpacki napędzane Polococtą i Mentosami wzbiły się w powietrze. Jednak zanim lemury zostaną rozłożone na łopatki, pingwiny muszą poważnie potrenować, bo jak wiadomo, trening czyni mistrza.

Pingwiny będą trenować w pobliskim parku na N ustawionych w rzędzie drzewach, ponumerowanych kolejnymi liczbami od 1 do N. Drzewo o numerze i ma wysokość H_i. Aby nie marnować cennego Polocotowego napędu, pingwiny postanowiły, że na razie będą tylko szybować, czyli zlatywać z korony wyższego drzewa na koronę niższego drzewa. I tak pingwiny mogą zszybować z drzewa o numerze x na drzewo o numerze y, gdy drzewo o numerze x jest wyższe oraz pomiędzy drzewami o numerach x i y wszystkie drzewa są niższe od drzewa o numerze x. Formalnie z drzewa o numerze x można zszybować do drzewa o numerze y, gdy H_y < H_x oraz H_i < H_x dla każdego i spełniającego min(x,y) < i < max(x,y).

Pingwiny chciałby oczywiście, aby po wspięciu się na określone drzewo “lot” trwał jak najdłużej dlatego, dla każdego ze swoich planów treningowych, chciałyby poznać maksymalną liczbę zszybowań. Plany treningowe pingwinów mają dwa różne typy:

• 1 X_i Y_i – pingwiny chcą wykonać możliwie wiele szybowań, by dostać się z drzewa o numerze X_i do drzewa o numerze Y_i lub z drzewa o numerze Y_i do drzewa o numerze X_i;

• 2 X_i – pingwiny chcą wykonać możliwie wiele szybowań, zaczynając z drzewa o numerze x.

Twoim zadaniem będzie napisanie programu, który na podstawie kolejnych wysokości drzew w parku dla każdego planu treningowego wyznaczy maksymalną liczbę szybowań.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i Q, oznaczające liczbę drzew oraz liczbę planów treningowych pingwinów. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych H_i pooddzielanych pojedynczymi odstępami i oznaczającymi wysokości kolejnych drzew w parku. W kolejnych Q wierszach znajdują się opisy planów treningowych, zgodne z formatem podanym w treści zadania.

Wyjście

Na wyjście należy wypisać dokładnie Q wierszy, w i-tym z nich powinna znaleźć się odpowiedź na i-te zapytanie. Jeśli wykonanie i-tego planu treningowego nie jest możliwe, to w i-tym wierszu wyjścia należy wypisać liczbę 0.

Ograniczenia

1 ≤ N, Q ≤ 100 000, 1 ≤ H_i, X_i, Y_i ≤ N.

Przykład

12 8
1 4 6 6 6 4 4 4 2 3 8 6
2 3
2 4 
1 7 11
1 7 9
2 5
1 1 11
2 7
1 9 12

2
0
2
0
3
3
0
0

Niestety fabryka Polococty została już wysadzona.

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.