Infoleague PreOJI 2023 9-10 | Minecraft

Enunt

Omeskok se joaca un minecraft de buget. Este un minecrat 2D in care exista doar 2 feluri de blockuri. Un block de pamant si un "block" de apa. Harta este reprezentata prin mai multe coloane de pamant de diferite inaltimi. Apa are aceleasi caracteristici ca in jocul original doar ca redus la 2 dimensiuni.
Astfel daca plasam un "block" de apa pe o coloana de pamant, aceasta va curge in stanga sau in dreapta doar daca coloana de pamant din directia miscarii are o inaltime mai mica sau egala cu coloana curenta. Diferit fata de jocul original nivelul apei se pastreaza constant (vezi desen). Omeskok are acum 2 intrebari:

1. Pentru fiecare coloana de pamant care ar fi aria structurii de apa formata daca am plasa un "block" de apa in varful ei, daca apa nu isi pastreaza nivelul?
2. Pentru fiecare coloana de pamant care ar fi aria structurii de apa formata daca am plasa un "block" de apa in varful ei, daca apa isi pastreaza nivelul?

Input

Prima linie va contine cerinta care trebuie rezolvata. Pe a doua linie se afla un numar $N$, numarul de coloane de pamant. Pe urmatoarea linie se afla o permutare de ordin $N$ reprezentand inaltimile coloanelor de pamant.

Output

Se va afisa un sire de lungime $N$ care reprezinta solutia cerintei.

Restrictii

• $1 \le N \le 10^6$
• Inaltimile coloanelor de pamant sunt o permutare a multimii {$1, 2, ... N$}
• Apa nu poate iesi din terenul de joc indiferent de situatie.
• Pentru rezolvarea corecta a primei cerinte se ofera 40p iar pentru a doua 60p

Observatie

Datorita faptului ca inputul este foarte mare pentru citire se recomanda folosirea instrucitonilor urmatoare la inceputul codului:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Exemplu

stdin

1
7
4 2 3 7 6 5 1

stdout

2 1 2 6 3 2 1

Explicatie

Daca am turna apa pe a patra coloana, terenul va arata asa:

Deci vor fi $6$ bucati de apa in cazul respectiv.

Exemplu

stdin

2
7
1 5 4 2 3 6 7

stdout

1 15 6 1 3 21 28

Explicatie

Daca am turna apa pe a treia coloana, terenul va arata asa:

Deci vor fi $6$ bucati de apa deci raspunsul pentru a treia coloana este $6$.