Stiva cu determinarea elementului maxim in O(1) — problema de informatică (dificultate medie)

Se citesc n operatii asupra unei stive initial vide, de tipul 'PUSH x', 'POP' sau 'MAX'. Operatia MAX trebuie sa afiseze maximul elementelor curente din stiva. Implementati stiva folosind o stiva auxiliara care retine, la fiecare nivel, maximul de pana atunci, astfel incat MAX sa functioneze in O(1). Se garanteaza ca MAX si POP nu se aplica pe o stiva vida.

Date de intrare: Pe prima linie se citeste n, numarul de operatii. Urmeaza n linii, fiecare continand o operatie. O operatie PUSH este urmata de valoarea intreaga x.
Date de iesire: Pentru fiecare operatie MAX, se afiseaza pe o linie separata maximul curent din stiva.
Restrictii: 1 <= n <= 200, valorile x sunt numere intregi, MAX si POP nu apar cand stiva este vida

Exemple

Exemplul 1

Intrare

6
PUSH 3
PUSH 5
MAX
PUSH 2
MAX
POP

Iesire

5
5

Exemplul 2

Intrare

5
PUSH 1
PUSH 2
PUSH 3
MAX
POP

Iesire