Fişierul intrare/ieşire:w.in, w.outSursăRMI 2018
AutorZoltan SzaboAdăugată delaurageorgescuLaura Georgescu laurageorgescu
Timp execuţie pe test0.7 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

W

Un vector de numere se spune că este de tip W dacă:

  • Consistă din patru segmente în ordine descrescătoare, ordine crescătoare, ordine descrescătoare, ordine crescătoare.
  • Ordinea nu este strictă, deci segmentele crescatoare şi descrescătoare pot include elementele consecutive egale.
  • Oricare două segmente consecutive au un capăt comun.
  • Orice segment conţine cel puţin două valori distincte.

De exemplu, vectorul (3 1 2 1 1 4) este de tip W, deoarece consistă din segmentele (3 1), (1 2), (2 1 1), (1 4). Vectorul (3 1 2 2 2 4) nu este de tip W. Acesta poate fi împărţit în segmentele (3 1), (1 2), (2 2 2), (2 4), dar segmentul (2 2 2) nu conţine cel puţin două valori distincte.

Dânduse un vector de N întregi, câte permutări distincte ale acestuia sunt de tip W? Două permutări (p1 p2 ... pN) şi (q1 q2 ... qN) se consideră distincte dacă exista o poziţie 1 ≤ i ≤ N astfel încât pi ≠ qi. In exemplul de mai sus, (3 1 2 1 1 4) trebuie numarată o singură dată, deoarece permutând cei 3 de 1 nu se creeaza permutări distincte.

Date de intrare

În fişierul de intrare w.in se află, pe prima linie, N. Pe a doua linie se găsesc cele N valori ale vectorului, separate prin spatii.

Date de ieşire

În fişierul de ieşire w.out se găseşte numărul de permutări distincte de tip W, modulo 1 000 000 007.

Restricţii

  • 5 ≤ N ≤ 300 000
  • Valorile elementelor din vector sunt numere naturale între 1 şi 1 000 000 inclusiv.
  • Pentru 20% din teste, vectorul contine doar două valori distincte.
  • Pentru alte 30% din teste, toate cele N elemente sunt distincte.

Exemplu

w.inw.out
5
3 1 4 2 3
6
7
1 2 2 2 3 4 4
72

Explicaţii

Pentru primul exemplu, cele 6 permutari de tip W sunt:
3 1 3 2 4
3 1 4 2 3
3 2 3 1 4
3 2 4 1 3
4 1 3 2 3
4 2 3 1 3

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?