Lista de probleme 3

Pentru o listă de numere naturale vom numi reprezentant al listei numărul care apare de cele mai multe ori în aceasta. În caz de egalitate (adică mai multe valori cu număr maxim de apariții) reprezentantul este suma acestor valori. Se dă o listă inițial vidă cu două tipuri de operații codificate în felul următor:

• 1 x – adăugăm un element nou cu valoarea x la sfârșitul listei și ne întrebăm ce valoare are reprezentantul după această modificare;
• 2 x – eliminăm primul element cu valoarea x din listă, ne întrebăm care este reprezentantul listei după eliminare și punem la loc elementul pe poziția lui.

Se dă șirul A de N numere naturale nenule A = (A[1], A[2], A[3], ..., A[N]). Numim secvență snake a șirului A o secvență S = (A[L], A[L+1], A[L+2], ..., A[R]) cu 1 ≤ L < R ≤ N cu proprietatea că fiecare poziție din șirul compress(S) este minim local sau maxim local. Să se determine câte perechi de poziții (L,R) cu 1 ≤ L < R ≤ N au proprietatea că secvența S = (A[L], A[L+1], A[L+2], ..., A_R) este snake.

La un concurs de pinball, în 2026, s-a întâmplat ceva inedit. Cei n participanți la concurs au obținut punctajele v[1], v[2], ..., v[n], numere naturale nenule. Pe lângă obișnuitele aplauze, au fost recompensați la finalul concursului cu bomboane. O persoană care a obținut punctajul x a primit un număr de bomboane egal cu numărul de divizori naturali ai lui x.
1. Știind că la începutul concursului, bugetul a fost de b bomboane, să se determine numărul nr de bomboane care au rămas după concurs.
2. Să se determine ce punctaj P cu proprietatea 1 ≤ P ≤ 6.000.000.000 ar trebui să obțină al (n+1)-lea participant, astfel încât să nu mai rămână nicio bomboană.