Cerința

În junglă cresc foarte mulți copaci, de diferite înălțimi. Fiind pasionat de copacii din junglă, Gigel a notat pe o foaie înălțimile la care pot ajunge copacii din junglă. Fiind închis în casă, își pune, ca orice copil normal, tot felul de întrebări bizare. El s-a gandit să planteze pomii în linie, într-o anumită ordine, și astfel a obținut N numere, v[1], v[2], ..., v[N], unde V[i] reprezintă înălțimea copacului i. Apoi i-au venit în minte două întrebări.

Mai întâi vrea sa afle câți copaci plantați înaintea copacului cu numărul de ordine i au înălțimile mai mici ca acesta.

A doua întrebare este mai speciala; Gigel se întreabă care ar fi dreptunghiul cu suprafața maximă liberă (adică neocupată de vreun copac) dacă ar încadra copacii într-o seră cu înălțimea egală cu înălțimea celui mai înalt copac plantat. Putem vizualiza sera ca pe un tablou bidimensional, cu colțul din stanga jos de coordonate (1,1) , iar cel din dreapta sus de coordonate (N,H), unde N este numărul de copaci, iar H este înâlțimea maximă a unui copac. În acest tablou copacul cu numărul de ordine i ocupă primele v[i] unități de pe coloana i, de jos in sus (v[i] reprezintă înălțimea copacului i).

Date de intrare

Programul citește de la tastatură un număr p, care poate avea valorile 1 sau 2, în funcție de cerința problemei.

Pentru p = 1, următorul rând conține numerele N q. Următorul rând conține n valori, a i -a valoare reprezentând înălțimea copacului cu numarul de ordine. Rândul următor conține q numere; pentru fiecare număr i se cere numarul de copaci plantați înaintea copacului cu numărul de ordine i cu înălțimi mai mici ca acesta.

Pentru p = 2, următorul rând va conține doar numărul N, iar ultimul rând va conține N valori reprezentând înălțimile copacilor.

Date de ieșire

Pentru p = 1 programul va afișa q linii; pe fiecare linie se va afla raspunsul pentru fiecare dintre cele q numere date.

Pentru p = 2 programul fa afișa singur numar, reprezentând raspunsul pentru cerinta 2 , adică dreptunghiul liber de arie maximă.

Restricții și precizări

• Pentru cerința 1, n ≤ 1000, iar pentru cerința 2, n ≤ 100.000
• înâlțimile copacilor vor fi numere naturale nenule mi mici decât 15.000
• 1 ≤ q ≤ 2*n
• Pentru 25 de puncte cerința este 1.

Exemplul 1:

Intrare

1
7 3
4 2 6 8 3 4 2
2 4 6

Ieșire

0
3
2

Exemplul 2:

Intrare

2
11
4 6 5 4 6 8 8 10 6 3 2

Ieșire

20

Explicație

Pentru exemplul 1: p=1 deci se rezolvă doar cerința 1. Inainte de copacul cu numărul de ordine 2 nu există copaci cu înalțimi mai mici, înainte de copacul cu numărul de ordine 4 există 3 copaci mai mici, iar înainte de copacul 6 există 2 copaci mai mici.

Pentru exemplul 2, sera ar arăta astfel:

o o o o o o o 1 o o
o o o o o o o 1 o o
o o o o o 1 1 1 o o
o o o o o 1 1 1 o o
o 1 o o 1 1 1 1 o o
o 1 1 o 1 1 1 1 o o
1 1 1 1 1 1 1 1 o o
1 1 1 1 1 1 1 1 1 o
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

Unde o reprezinta zona liberă, iar 1 reprezintă o zona ocupată de copac. Suprafața dreptunghiulară maximă este de 20 de unități.