Alienii

Nulla exempla. Nulla problemata.

Sistemele Unite Extraterestre (S.U.E) au dezvoltat o nouă tehnologie ce poate transforma un întreg oraș din trei dimensiuni în două. Încântați de noua descoperire, aceștia și-au ales prima țintă: orașul Constanța! Astfel, frumosul oraș portuar a devenit un șir de $N$ blocuri cu înălțimile $h_1, h_2, \dotsc , h_N$ (unități extraterestre). În urma experimentului, extratereștrii vor dori să extragă probe din vârful blocurilor folosind o sondă. Renumiții cercetători constănțeni doresc să oprească planul S.U.E. Astfel, ei plănuiesc să construiască scuturi galactice deasupra unor blocuri, pentru ca utilizarea tehnologiei dezvoltate de S.U.E. să fie imposibilă. Construcția unui scut galactic începe de pe acoperișul unui bloc $i$ și poate proteja un interval continuu de blocuri $[l, r]$, unde $1 \leq l \leq i \leq r \leq N$. Totuși, acest interval de blocuri trebuie să respecte o condiție esențială: $h_l \le h_{l+1} \le \dotsb \le h_i \ge \dotsb \ge h_{r-1} \ge h_r$. De asemenea, scuturile dezvoltate de constănțeni au și un nivel $T$ de tehnologie.

• Dacă $T=1$, atunci $l=i=r$, pentru orice scut început de pe acoperișul blocului $i$, unde $[l, r]$ este intervalul de blocuri apărate de scut.
• Dacă $T=2$, atunci $l \le i=r$, pentru orice scut început de pe acoperișul blocului $i$, unde $[l, r]$ este intervalul de blocuri apărate de scut.
• Dacă $T=3$, atunci $l \le i \le r$, pentru orice scut început de pe acoperișul blocului $i$, unde $[l, r]$ este intervalul de blocuri apărate de scut.

Pentru a dezvolta o strategie de apărare, cercetătorii constănțeni trebuie să afle, pentru fiecare bloc cu indice $i$, suma $S_i$ a dimensiunilor tuturor scuturilor ce pornesc din blocul $i$ și respectă condițiile de mai sus.

Cerință

Ajutați cercetătorii să oprească agresiunile S.U.E asupra Constanței, calculând cele $N$ sume.

Date de intrare

Pe prima linie a fișierului de intrare alienii.in se află două numere naturale: $T$, nivelul de tehnologie al scuturilor galactice folosite, și $N$, numărul de blocuri.
Pe cea de-a doua linie se află $N$ numere naturale, separate printr-un spațiu, reprezentând înălțimea blocurilor din Constanța.

Date de ieșire

Pe prima linie a fișierului de ieșire alienii.out se vor găsi $N$ numere naturale: $S_1, S_2, \cdots S_N$.

Restricții și precizări

• $1 \leq N \leq 500 \ 000$;
• $1 \leq h_i \leq 10^9$;
• Dimensiunea unui scut ce apără intervalul de blocuri $[l, r]$ este egală cu numărul de blocuri din acesta;

Exemplul 1

alienii.in

1 5
4 7 2 3 9

alienii.out

1 1 1 1 1

Exemplul 2

alienii.in

2 5
4 7 2 3 9

alienii.out

1 3 1 3 6

Explicație

Câteva intervale de blocuri valide pentru acest exemplu sunt $[1, 2]$, $[3, 5]$, $[4, 4]$, cu dimensiunile $2$, $3$, respectiv $1$.

Exemplul 3

alienii.in

3 5
4 7 2 3 9

alienii.out

1 8 1 3 6

Explicație

Se poate observa că, în cadrul calculării sumei dimensiunilor scuturilor construite la blocul $2$, intervalul de blocuri $[1, 3]$ se va lua în considerare în acest caz, față de exemplul al doilea.