MaxMin2

Rolul meu nu era aici...

Buzdi s-a săturat să fie simplu, nervos sau primar. El hotărăște să se relaxeze, urmărind categoria sa preferată de probleme de pe magnificul site, numită maxime și minime. Deoarece simte că această categorie merită și puțin noroc, Buzdi se gândește la aceasta împreună cu numărul lui norocos, $2$. Prin marea adunătură de idei din mintea lui (nu e prea mare...), acesta găsește două cerințe care chiar merită să fie puse într-un concurs de informatică (foreshadowing...).

Se dă un șir $A$ de $N$ numere naturale. Fie $S$ un subșir nevid al lui $A$. Se definește următoarea funcție:

Mai simplu, funcția $f(S)$ returnează suma dintre valoarea maximă din subșirul $S$ și valoarea minimă din subșirul $S$ la pătrat.

Cerință

1. Să se determine valoarea maximă $f(SB)$, unde $SB$ este o subsecvență din șirul $A$, precum și numărul de subsecvențe pentru care $f(SB)$ este maxim.
2. Să se calculeze $\sum_{S \subseteq A} f(S)$. Cu alte cuvinte, să se calculeze suma valorilor returnate de funcția $f$ pentru fiecare subșir $S$ din $A$. Deoarece această sumă este foarte mare, se va determina restul împărțirii acesteia la $10^9 + 7$.

Date de intrare

Pe prima linie a fișierului de intrare maxmin2.in se găsesc două numere naturale, $C$ și $N$, separate printr-un spațiu, reprezentând cerința ce trebuie rezolvată și lungimea șirului $A$. Pe următoarea linie se găsesc $N$ numere naturale, separate printr-un spațiu, reprezentând elementele șirului $A$.

Date de ieșire

• Dacă $C = 1$, atunci pe prima linie a fișierului de ieșire maxmin2.out se vor găsi două numere naturale, separate printr-un spațiu, reprezentând răspunsul cerinței $1$.
• Dacă $C = 2$, atunci pe prima linie a fișierului de ieșire maxmin2.out se va găsi un singur număr natural, reprezentând răspunsul cerinței $2$.

Restricții și precizări

• $1 \leq C \leq 2$;
• $1 \leq N \leq 200 \ 000$;
• $1 \leq A_i \leq 10^9, 1 \leq i \leq N$;
• Șirul $A$ este indexat de la $1$;
• Un subșir al șirului $A$ este un șir $S = (A_{i_1}, A_{i_2}, A_{i_3}, \dots, A_{i_k})$ cu $1 \leq i_1 < \dots < i_k \leq N$;
• O subsecvență a șirului $A$ este un șir $SB = (A_l, A_{l + 1}, A_{l + 2}, \dots, A_r)$ cu $1 \leq l \leq r \leq N$;

  #	Punctaj	Restricții
  0	0	Exemplele
  1	14	$C = 1 \\ 1 \leq N \leq 2000$
  2	17	$C = 1$
  3	17	$C = 2 \\ 1 \leq N \leq 20$
  4	11	$C = 2$ și toate valorile din șirul $A$ sunt egale
  5	20	$C = 2 \\ 1 \leq N \leq 2000$
  6	21	$C = 2$

Exemplul 1

maxmin2.in

1 6
4 5 2 5 5 1

maxmin2.out

100 4

Explicație

$C = 1$, deci se va rezolva doar cerința $1$.
Valoarea maximă $f(SB)$ este egală cu $100$. Subsecvențele $SB$ pentru care $f(SB) = 100$ sunt formate de indicii din intervalele $[2, 2], [4, 4], [5, 5], [4, 5]$.
De asemenea, se observă că subșirul $\{5, 5, 5\}$ format de indicii $\{2, 4, 5\}$ nu reprezintă un răspuns valid, deoarece acesta nu este o subsecvență.

Exemplul 2

maxmin2.in

2 3
4 2 3

maxmin2.out

262

Explicație

$C = 2$, deci se va rezolva doar cerința $2$.
Sunt $7$ subșiruri nevide în șirul $A$.

1. $S = \{4\} \rightarrow f(S) = (max(S) + min(S))^2 = (4 + 4)^2 = 8^2 = 64$.
2. $S = \{2\} \rightarrow f(S) = (max(S) + min(S))^2 = (2 + 2)^2 = 4^2 = 16$.
3. $S = \{3\} \rightarrow f(S) = (max(S) + min(S))^2 = (3 + 3)^2 = 6^2 = 36$.
4. $S = \{4, 2\} \rightarrow f(S) = (max(S) + min(S))^2 = (4 + 2)^2 = 6^2 = 36$.
5. $S = \{4, 3\} \rightarrow f(S) = (max(S) + min(S))^2 = (4 + 3)^2 = 7^2 = 49$.
6. $S = \{2, 3\} \rightarrow f(S) = (max(S) + min(S))^2 = (3 + 2)^2 = 5^2 = 25$.
7. $S = \{4, 2, 3\} \rightarrow f(S) = (max(S) + min(S))^2 = (4 + 2)^2 = 6^2 = 36$.

Suma acestor valori este egală cu $262$.