# PBinfo #3636 – Hill Climb – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
În acest univers virtual, până și dealurile pot fi modificate la cel mai mic ordin al combatanților ezoterici. 

Se da un vector a cu n numere naturale și scopul nostru este să-l transformăm într-un vector descrescător. Pentru a-l face descrescător, avem la dispoziție următoarea operatie:

La o parcurgere a șirului de la poziția 1 la poziția n, vom proceda în felul următor pentru fiecare poziție i, în ordine crescătoare: dacă a[i] ≤ a[i+1], vom atribui lui a[i] = a[i+1].

De exemplu, dacă avem vectorul [4, 1, 5, 3, 3], începem la poziția 1, apoi mergem la poziția 2, valoarea lui a[2] devine 5, apoi mergem la poziția 3, apoi la poziția 4 și în cele din urmă la poziția 5.

După modificări, vectorul va avea următoarele valori: [4, 5, 5, 3, 3].

Trebuie să aflați câte parcurgeri sunt necesare pentru a transforma vectorul într-un vector descrescător.

Date de intrare
Fiecare test conține mai multe teste. Prima linie conține numărul de teste t.

Fiecare test conține pe prima linie numărul n, iar apoi n numere naturale, separate prin spații.

Date de ieșire
Programul va afișa pe ecran pentru fiecare linie x, reprezentând numărul de parcurgeri cerut în enunț.

Restricții și precizări

1 ≤ t ≤ 10
2 ≤ n ≤ 100000
cele n numere citite sunt cuprinse între -1.000.000.000 și 1.000.000.000
pentru teste valorând 20 de puncte, 2 ≤ n ≤ 1000

Exemplu:
Intrare

2
5
4 1 5 3 3
4
5 5 4 2
Ieșire

2
0
Explicație
Primul test necesită două parcurgeri: [4, 1, 5, 3, 3] -> [4, 5, 5, 3, 3] -> [5, 5, 5, 3, 3]

Cel de-al doilea test conține un vector care este deja descrescător, așa că răspunsul este deja 0.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
#define int ll
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
ifstream iredirect;
ofstream oredirect;
const string file = "data";
const ll INF = 9223372036854775807ll;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}, dy[] = {0, 0, 1, -1, 1, -1, 1, -1}, inf = 2147483647;
void prepare_IO()
{
	#ifndef WATER_ADDICT
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
		cout.tie(NULL);
	#else
		iredirect.open(file+".in");
		cin.rdbuf(iredirect.rdbuf());
		// oredirect.open(file+".out");
		// cout.rdbuf(oredirect.rdbuf());
	#endif
}
void solve()
{
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; ++i)
		cin >> v[i];
	int ans = 0, mx = v[n-1], pos = n-1;
	for (int i = n-2; i >= 0; --i){
		if (v[i] >= mx) {
			mx = v[i];
			pos = i;
		}
		ans = max(ans, pos-i);
	}
	cout << ans << "\n";
}
signed main()
{
	prepare_IO();
	int number_of_tests = 1;
	cin >> number_of_tests;
	for (int testcase = 1; testcase <= number_of_tests; ++testcase)
		solve();
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3636)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3636/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3636/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)