Secventa 6
Problema cere determinarea numarului perechilor de indici i, j (i < j) pentru care ak < ai si ak < aj, unde i < k < j. Sa consideram multimea T a indicilor care verifica relatia de mai sus pentru pozitia p a sirului dat. Daca avem t1 si t2 apartinand lui T, t1 < t2, cum at1 < ak cu t1 < k < p, rezulta ca at2 < at1; asadar multimii ordonate (crescator) T ii corespune o multime ordonate (descrescator) A'. Multimea A' poate fi construita cu ajutorul unei stive sortate, la pasul p sunt scoase din stiva elemente mai mici sau egale decat ap si este introdus elemntul ap. Stiva construita astfel contine elementele corespunzatoare indicilor multimii T prezentate mai sus, dar contine si elemente in plus (este respectata numai una din conditiile problemei). Observam ca ultimul element care respecta si a doua conditie este, in ordinea stivei sortate, primul element mai mare sau egal decat ap. In concluzie numarul de indici care respecta conditia pentru pozitia p este egala cu numarul de elemente scoase din stiva sortata la introducerea elementului ap +1 daca ultimul element scos din stiva este diferit de ap.
