Cromatic

Fie $a = (a_1, a_2, \dots, a_n)$ un șir de $n$ numere întregi. Pentru fiecare $k \in \{1,2,\dots,n\}$, definim $min_k=\min\{a_1, a_2, \dots ,a_k\}$ și $max_k=\max\{a_1, a_2, \dots ,a_k\}$. Astfel, asociem șirului $a$ un alt șir de intervale închise $minmax = ([min_1, max_1], [min_2, max_2], \dots, [min_n, max_n])$.

Vom spune că șirul $a$ este un șir cromatic dacă și numai dacă elementele șirului $minmax$ sunt distincte două câte două, adică nu există două intervale identice în șir.

De exemplu, dacă $a = (7, 4, 9)$, atunci șirul $minmax$ este $\Bigl([7,7], [4,7], [4,9]\Bigr)$. Cum nu există $2$ intervale identice în $minmax$, șirul $a$ este cromatic. În schimb, dacă $a=(4,9,7)$, atunci șirul $minmax$ este $\Bigl([4,4], [4,9], [4,9]\Bigr)$. Intervalul $[4, 9]$ se repetă, deci șirul $a$ nu este cromatic.

Considerăm toate șirurile cromatice distincte ce se pot forma prin rearanjarea elementelor șirului $a$ și le ordonăm lexicografic. Notăm cu $NSC$ numărul de șiruri astfel obținute. De exemplu, dintre cele 6 permutări ale șirului $a = (7,4,9)$, numai $NSC = 4$ sunt cromatice:

1. $(4, 7, 9)$;
2. $(7, 4, 9)$;
3. $(7, 9, 4)$;
4. $(9, 7, 4)$.

Cerință

Dându-se un șir $a$, nu neapărat cromatic, să se determine:

1. Numărul de șiruri cromatice $NSC$ ce se pot forma prin rearanjarea elementelor șirului $a$. Întrucât acest număr poate fi foarte mare, se cere $NSC$ modulo $1 \ 000 \ 000 \ 007$.
2. Știind că șirul $a$ este cromatic, să se determine poziția $p\in\left\{1,2,\dots,\textit{NSC}\right\}$ a șirului $a$ în lista ordonată lexicografic a tuturor permutărilor cromatice ale lui $a$.
3. Dat fiind $q\in\left\{1,2,\dots,NSC\right\}$, să se determine cel de-al $q$-lea șir cromatic în ordine lexicografică ce se poate obține prin rearanjarea elementelor șirului $a$.

Date de intrare

Fișierul de intrare cromatic.in conține pe prima linie un număr natural $c\in\left\{1,2,3\right\}$, reprezentând numărul cerinței de rezolvat:

1. Dacă $c = 1$, pe linia a doua vom avea un număr natural $n$, iar pe linia a treia vom avea $n$ numere naturale separate prin spații, reprezentând un șir nu neapărat cromatic.
2. Dacă $c = 2$, pe linia a doua vom avea un număr natural $n$, iar pe linia a treia vom avea $n$ numere naturale separate prin spații, reprezentând un șir cromatic.
3. Dacă $c = 3$, linia a doua va conține numerele $n$ și $p$ separate prin spații, iar linia a treia va conține $n$ numere distincte separate prin spații, reprezentând un șir nu neapărat cromatic.

Date de ieșire

Fișierul de ieșire cromatic.out trebuie să conțină o singură linie, pe care se va afișa, în funcție de numărul cerinței de rezolvat:

1. Dacă $c$ = $1$, numărul natural $NSC$ modulo $1 \ 000 \ 000 \ 007$;
2. Dacă $c$ = $2$, numărul natural $p$, ce reprezintă poziția șirului $a$ în lista ordonată lexicografic a tuturor șirurilor cromatice obținute prin rearanjarea elementelor șirului citit;
3. Dacă $c$ = $3$, un șir de $n$ numere naturale, separate prin spații, ce reprezintă cel de-al $q$-lea șir cromatic în ordine lexicografică care se poate obține prin rearanjarea elementelor șirului $a$.

Restricții și precizări

• $2 \leq n \leq 300 \ 000$
• $-1 \ 000 \ 000 \ 000 \leq a_i \leq 1 \ 000 \ 000 \ 000$
• $1 \leq p, q \leq 1 \ 000 \ 000 \ 000$
• $p,q\in\bigl\{1,2,\dots,\textit{NSC}\}$

Exemplul 1

cromatic.in

1
4
1 5 3 8

cromatic.out

8

Explicație

Avem 8 șiruri cromatice distincte:

1. $1 \ 3 \ 5 \ 8$
2. $3 \ 1 \ 5 \ 8$
3. $3 \ 5 \ 1 \ 8$
4. $3 \ 5 \ 8 \ 1$
5. $5 \ 3 \ 1 \ 8$
6. $5 \ 3 \ 8 \ 1$
7. $5 \ 8 \ 3 \ 1$
8. $8 \ 5 \ 3 \ 1$

Exemplul 2

cromatic.in

2
4
5 3 1 8

cromatic.out

5

Explicație

În lista ordonată lexicografic, șirul citit se găsește pe poziția $5$.

Exemplul 3

cromatic.in

3
4 7
5 3 1 8

cromatic.out

5 8 3 1

Explicație

A $7$-a soluție în ordine lexicografică este $5 \ 8 \ 3 \ 1$.