volei

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 volei.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 despărţite prin câte un spaţiu, 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 despărţite prin câte un spaţiu, 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 volei.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 între paranteze.

Restricții și precizări

• $1 \leq n, m \leq 2 \ 000$
• Înălțimile fetelor și a băieților nu depășesc valoarea $1\ 000$.
• Dacă există mai multe posibilităţi de a insera $k$ băieţi în joc, se va scrie una singură.
• Dacă numerele reprezentând înălţimile nu vi se par plauzibile, atunci puteţi considera că ele reprezintă coeficientul de inteligenţă al fiecărei persoane.
• Pentru afişarea valorii corecte a numărului $k$ se acordă 40 de puncte, iar pentru soluţia completă ($k$ maxim şi configuraţia corectă a celor $n + k$ înălţimi ale jucătorilor) se acordă 100 de puncte.

Exemplul 1

volei.in

4
15 11 72 31
3
20 50 25

volei.out

2
15 (20) 11 72 31 (50)

Explicatii

O altă soluție corectă este:

$2$
$15 \ (25) \ 11 \ 72 \ 31 \ (50)$

Exemplul 2

volei.in

6
15 8 20 19 16 30
3
20 30 16

volei.out

3
15 (16) 8 (30) 20 19 (20) 16 30

Explicatii

O altă soluție corectă este:

$3$
$15 \ (16) \ 8 \ 20 \ (30) \ 19 \ (20) \ 16 \ 30$;

Exemplul 3

volei.in

4
10 20 15 100
2
20 8

volei.out

0
10 20 15 100