Câţiva băieţi, după un fotbal mic, au hotărât să participe la jocul liber de volei al fetelor. Fetele sunt aşezate în cerc şi nu îşi schimbă locurile între ele. Un băiat se poate ataşa jocului fetelor numai dacă se aşează între două fete şi este mai înalt (strict) decât amândouă.

Cerinţă

Cunoscând numărul de fete şi înălţimea fiecăreia, în ordinea în care se află ele pe cerc, numărul băieţilor şi înălţimea fiecăruia, se cere să se determine un număr maxim de băieţi care pot participa la joc şi poziţia ocupată de fiecare pe cerc.

Date de intrare

Din fişierul text de intrare volei1.in se citesc:
– de pe prima linie un număr natural n, numărul de fete din joc;
– de pe cea de a doua linie, n numere naturale nenule de cel mult 3 cifre fiecare, despărţite prin câte un spaţiu, numere reprezentând înălţimile fetelor, în ordinea de pe cerc, în sensul acelor de ceasornic, pornind de la o fată oarecare;
– de pe cea de a treia linie, un număr natural m, numărul de băieţi care vor să intre în joc;
– de pe cea de a patra linie, m numere naturale nenule de cel mult 3 cifre fiecare, despărţite prin câte un spaţiu, numere reprezentând înălţimile băieţilor care vor să intre în joc.

Date de ieşire

În fişierul text de ieşire volei1.out se scriu:
– pe prima linie un număr natural k, reprezentând numărul maxim de băieţi care pot participa la joc;
– pe linia următoare, n+k numere naturale, despărţite prin câte un spaţiu, numere reprezentând înălţimile jucătorilor de volei, în ordinea de pe cerc, în sensul acelor de ceasornic, pornind de la aceeaşi fată din fişierul de intrare, înălţimile băieţilor fiind scrise cu semnul ′-′ (minus) în faţă.

Restricţii

0 < n <= 2000
0 < m <= 2000

Exemple

volei1.in	volei1.out	Explicaţii
4 15 11 72 31 3 20 50 25	2 15 -20 11 72 31 -50 sau (vezi figura) 2 15 -25 11 72 31 -50
6 15 8 20 19 16 30 3 20 30 16	3 15 -16 8 -30 -20 19 -20 16 30 sau 3 15 -16 8 20 -30 19 -20 16 30
4 10 20 15 100 2 20 8	0 10 20 15 100

autor: Prof. Rodica Pintea

propunător: Prof. Marinel Şerban

Liceul de Informatică “Grigore Moisil”

marinel_serban@yahoo.com