== include(page="template/taskheader" task_id="lumanari") ==

In camera magica toata lumina trebuie sa provina de la lumanari. Vrem sa luminam camera $N$ zile, numerotate convenabil de la $1$ la $N$. Stim ca in ziua $i$ trebuie sa aprindem $i$ lumanari pentru a lumina camera. La sfarsitul zilei vom stinge lumanarile aprinse. Stim ca daca tinem o lumanare aprinsa timp de o zi, inaltimea acesteia va scadea cu $1$. Dandu-vi-se $N$, numarul de zile in care trebuia sa luminam camera, si $M$, numarul de lumanari disponibile impreuna cu inaltimile lor, afisati in output $"DA"$ sau $"NU"$ (fara ghilimele) daca putem lumina camera timp de $N$ zile cu lumanarile date

In camera magica toata lumina trebuie sa provina de la lumanari. Vrem sa luminam camera timp de $N$ zile, numerotate convenabil de la $1$ la $N$. Stim ca in ziua $i$ trebuie sa aprindem $i$ lumanari pentru a lumina camera. La sfarsitul zilei vom stinge lumanarile aprinse. Stim ca daca tinem o lumanare aprinsa timp de o zi, inaltimea acesteia va scadea cu $1$. Calculati valoarea maxima pe care o poate lua $N$.

h2. Date de intrare

Fişierul de intrare $lumanari.in$ va contine pe prima linie numarul $M$ cu semnificatia din enunt. Pe a doua linie a fisierului de intrare se vor gasi $M$ numere naturale reprezentand inaltimile celor $M$ lumanari. Pe a treia linie se va gasi numarul $T$, reprezentand numarul de valori $N$ pentru care ne intereseaza raspunsul. A patra linie va contine $T$ valori de $N$.

Fişierul de intrare $lumanari.in$ va contine pe prima linie numarul $M$ cu semnificatia din enunt. Pe a doua linie a fisierului de intrare se vor gasi $M$ numere naturale reprezentand inaltimile celor $M$ lumanari.

h2. Date de ieşire

În fişierul de ieşire $lumanari.out$ se vor afla $T$ linii, linia $i$ continand $DA$ sau $NU$ ca raspuns la a $T$-a intrebare.

În fişierul de ieşire $lumanari.out$ se va afla valoarea maxima a lui $N$.

h2. Restricţii
* $1 ≤ M ≤ 200 000$
* $1 ≤ T ≤ 1 000$
* $1 ≤ N ≤ M$

* Daca o lamanare ajunge la inaltimea $0$, nu mai poate fi folosita.

h2. Exemplu
table(example). |_. lumanari.in |_. lumanari.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6
1 3 4 5 6 1
| 5

|
h3. Explicaţie

...

Vom arde lumanarile in urmatorul mod in cele $5$ zile:
$Ziua 0: 1 3 4 5 6 1$
$Ziua 1: 0 3 4 5 6 1$
$Ziua 2: 0 2 3 5 6 1$
$Ziua 3: 0 2 2 4 5 1$
$Ziua 4: 0 1 1 3 4 1$
$Ziua 5: 0 0 0 2 3 0$

== include(page="template/taskfooter" task_id="lumanari") ==
 

== include(page="template/taskfooter" task_id="lumanari") ==