Fişierul intrare/ieşire:	fpwl.in, fpwl.out	Sursă	FMI No Stress 2012
Autor	Din Folclor	Adăugată de	Serban Andrei Stan •savim
Timp execuţie pe test	1.5 sec	Limită de memorie	66048 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Fpwl

Pentru un sir de numere a₁,a₂,...,a_N notam secventa poloneza a sa ca fiind secventa s₁,s₂,...,s_N-1 de simboluri <, > sau =. Simbolul s_i al secventei reprezinta relatia dintre a_i si a_i+1. De exemplu secventa poloneza a sirului 2,4,3,3,5,3 este <,>,=,<,>.

Spunem ca sirul b₁,b₂,...,b_N+1 cu secventa poloneza s₁,s₂,...,s_N realizeaza o alta secventa poloneza s'₁,s'₂,...,s'_K daca oricare ar fi i de la 1 la N s_i=s'_{(i-1) mod K + 1}. Altfel spus secventa s₁,s₂,...,s_N se poate obtine din secventa s'₁,s'₂,...,s'_K repetand aceasta secventa de cateva ori si apoi eliminand sufixul corespunzator. De exemplu secventa 2,4,3,3,5,3 realizeaza urmatoarele secvente poloneze:

• <,>,=
• <,>,=,<,>
• <,>,=,<,>,<,<,=
• <,>,=,<,>,=,>,>

si multe altele.

Vi se da un sir de numere a₁,a₂,...,a_N si o secventa poloneza s₁,s₂,...,s_K. Voi trebuie sa aflati cel mai lung subsir al lui a a_i1,a_i2,...,a_iM (1≤i1≤i2≤..≤iM) care realizeaza secventa poloneza s.

Date de intrare

Prima linie a fisierului fpwl.in contine pe prima linie 2 numere intregi N si K separate printr-un singur spatiu reprezentand lungimea sirului (a_i), respectiv (s_j)
A doua linie contine N numere intregi a₁,a₂,...,a_N separate prin cate un spatiu reprezentand sirul a.
A treia si ultima linie contine K simboluri de forma <,> sau = reprezentand secventa poloneza s

Date de ieşire

În fişierul de ieşire fpwl.out trebuie sa contina 2 linii.
Pe prima linie trebuie sa se gaseasca M, lungimea celui mai lung subsir al lui a care realizeaza secventa poloneza s.
A doua si ultima linie trebuie sa contina M elemente a_i1,a_i2,...,a_iM reprezentand un astfel de subsir.

Restricţii

• 1 ≤ N, K ≤ 500.000
• 1 ≤ a_i ≤ 1.000.000

Exemplu

Cum se trimit solutii?