Rezolvare PBinfo #3736

Se dă un șir format din N numere naturale nenule. Elementele șirului sunt numerotate de la stânga la dreapta începând cu poziția 1.

Cerința

Scrieți un program care să determine răspunsul pentru întrebări de următoarele tipuri:
1. Care este cea mai din stânga poziție care conține o valoare strict mai mare decât toate cele din dreapta sa? – întrebare de tipul 1
2. Care sunt pozițiile care conțin valori strict mai mari decât toate cele din stânga lor? – întrebare de tipul 2
3. Dacă fiecărui element aflat între prima și ultima apariție a maximului i-am mări valoarea pentru a ajunge egal cu maximul, care este suma totală a valorilor adăugate? – întrebare de tipul 3

Date de intrare

Fișierul de intrare sir.in conține pe prima linie un număr C (care poate fi 1, 2 sau 3), indicând tipul întrebării. Pe linia a doua se află un număr natural N, reprezentând numărul de elemente din șir. Pe a treia linie a fișierului de intrare se află N numere naturale, reprezentând elementele șirului, date de la stânga la dreapta (cel mai din stânga are poziția 1 și cel mai din dreapta are poziția N). Numerele de pe această linie sunt separate prin câte un spațiu.

Date de ieșire

Dacă C = 1, fișierul de ieșire sir.out trebuie să conțină un număr natural ce reprezintă răspunsul la o întrebare de tipul 1. Dacă C = 2, fișierul de ieșire trebuie să conțină, separați prin câte un spațiu și în ordine crescătoare, indicii determinați ca răspuns la o întrebare de tipul 2. Dacă C = 3, fișierul de ieșire trebuie să conțină un număr ce reprezintă răspunsul la o întrebare de tipul 3.

Restricții și precizări

• 1 ≤ C ≤ 3
• 1 ≤ N ≤ 100.000
• Numerele din șirul dat sunt cuprinse între 1 și 10.000, inclusiv.
• Pentru teste în valoare de 24 de puncte avem C = 1.
• Pentru teste în valoare de 32 de puncte avem C = 2.
• Pentru teste în valoare de 44 de puncte avem C = 3.

Exemplul 1:

sir.in

1
7
3 2 2 5 3 5 4

sir.out

6

Explicație

Cea mai din stânga poziție a unei valori care este mai mare decât toate cele din dreapta sa este 6 (acolo unde se află valoarea 5)

Exemplul 2:

sir.in

2
7
3 2 2 5 3 5 4

sir.out

1 4

Explicație

1 și 4 sunt pozițiile unde se află valori mai mari decât toate cele din stânga lor.

Exemplul 3:

sir.in

3
8
3 2 2 5 3 1 5 4

sir.out

6

Explicație

Maximul fiind 5, conform explicației de la întrebarea de tipul 3, trebuie mărite două elemente pentru a ajunge egale cu 5. Acestea sunt cel aflat pe poziția 5 (de mărit cu 2) precum și cel de pe poziția 6 (de mărit cu 4). Suma valorilor cu care avem de mărit este 2 + 4 = 6.

Exemplul 4:

sir.in

3
5
3 2 7 5 3

sir.out

0

Explicație

Maximul este 7 și apare o singură dată, deci nu se mai mărește nicio valoare.