dominew

Algoritmul, pas cu pas

Gândește-te ce înseamnă „cea mai mică poziție care păstrează ordinea crescătoare". O piesă $v$ trebuie să stea după toate piesele mai mici ca ea și înaintea celor mai mari. Dacă în șir sunt $k$ piese strict mai mici decât $v$, ele ocupă pozițiile $1, 2, \dots, k$, iar locul lui $v$ este imediat după ele: poziția $k+1$. Atât. Toată problema se reduce la a număra repede câte piese sunt mai mici.