Fişierul intrare/ieşire:	bitone.in, bitone.out	Sursă	Cerc informatică Vianu
Autor	Cristian Francu	Adăugată de	Cristian Francu •francu
Timp execuţie pe test	1.6 sec	Limită de memorie	8500 kbytes
Scorul tău	N/A	Dificultate	2/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Bitone

O secvenţă de numere întregi se numeşte bitonă dacă este crescătoare la început, iar apoi descrescătoare. Mai precis, o secvenţă a₁, a₂, ..., a_n este bitonă dacă:

• este o secvenţă nedescrescătoare: a₁ ≤ a₂ ≤ ... ≤ a_n sau
• este o secvenţă necrescătoare: a₁ ≥ a₂ ≥ ... ≥ a_n sau
• exista un indice i pentru care a₁ ≤ a₂ ≤ ... ≤ a_i ≥ a_i+1 ≥ ... ≥ a_n

Cerinţă

Dată o secvenţă de numere întregi a₁, a₂, ..., a_n şi nişte întrebări de forma (i, j) să se răspundă pentru fiecare întrebare dacă subsecvenţa a_i, a_i+1, ..., a_j este bitonă.

Date de intrare

Fişierul de intrare bitone.in conţine pe prima linie numărul de numere din secvenţă, n. Pe a doua linie conţine cele n numere ale secvenţei, separate de spaţii. Pe a treia linie se află numărul de întrebări q. Pe următoarele q linii se vor găsi cîte două numere i j separate prin spaţiu, reprezentînd întrebările la care se cere răspuns.

Date de ieşire

Fişierul de ieşire bitone.out va conţine o singură linie cu q caractere 0 sau 1, fără spaţii între ele, caractere ce reprezintă răspunsurile la întrebări. Pentru fiecare întrebare veţi răspunde 1 dacă subsecvenţa este bitonă, sau 0 în caz contrar.

Restricţii

• 1 ≤ n ≤ 1.000.000
• -2.000.000.000 ≤ a_i ≤ 2.000.000.000
• 1 ≤ q ≤ 1.000.000
• 1 ≤ i ≤ j ≤ n

Exemple