Koniec kola: 17. máj 2021 23:59
1 deň
Počet bodov:
Popis:  12b
Program:  8b

Gašpar už od samej nudy naozaj nevie, čo robiť. Absentuje akákoľvek rozumná myšlienka. A tak otvorí tašku v kúte izby a rozmýšľa, čo by len mohol použiť. Kalkulačka? Stará plesnivá desiata? Zbierka úloh KSP? Vodná pištol? Lano? Lano!

Gašpar už vie, čo spraví. Natiahne lano medzi niektoré stromy v záhrade, bude sa po ňom prechádzať a naučí sa na lane robiť nejaké tie akrobatické kúsky.

Teraz však Gašpar stojí pred závažnou otázkou: ktoré dvojice stromov spojiť povrazom? Samozrejme, že natiahnuté povrazy sa nesmú križovať. Okrem toho sú z rôznych dôvodov niektoré dvojice stromov vylúčené. Popri tomto všetkom by Gašpar chcel vytvoriť, čo najviac spojení.

Pomôžte Gašparovi s týmto problémom!

Úloha

V záhrade sú dva záhony obsahujúce po \(n\) stromov. Stromy v ľavom záhone majú priradené čísla \(p_1, \dots, p_n\). Stromy v pravom záhone majú priradené čísla \(q_1, \dots, q_n\). Platí, že \(p_1, \dots, p_n\) a \(q_1, \dots, q_n\) sú permutáciami čísel \(1, \dots, n\).

Gašpar chce natiahnuť lano medzi niektorými dvojicami stromov tak, aby platilo:

  • každé spojenie vedie medzi nejakým stromom z ľavého záhonu a nejakým stromom z pravého záhonu,
  • na každý strom je napojené nanajvýš \(1\) lano,
  • natiahnuté povrazy sa nekrižujú,
  • ak sú stromy \(p_i\) a \(q_j\) spojené povrazom, tak platí \(|p_i-q_j| \leq 4\).

Zistite, koľko najviac spojení môže Gašpar vytvoriť.

Formát vstupu a výstupu

Na prvom riadku vstupu je číslo \(n\) – počet stromov v jednom záhone, \(1 \leq n \leq 300\,000\).

Druhý riadok vstupu obsahuje \(n\) čísel \(p_1, \dots, p_n\) – čísla stromov v prvom záhone. \(p_1, \dots, p_n\) sú permutáciou čísel \(1, \dots, n\).

Tretí riadok obsahuje \(n\) čísel \(q_1, \dots, q_n\) – čísla stromov v druhom záhone. \(q_1, \dots, q_n\) sú permutáciou čísel \(1, \dots, n\).

Vypíste jeden riadok obsahujúci jedno číslo – najväčší počet lán, ktoré môže Gašpar medzi stromami natiahnuť.

Hodnotenie

Vstupy sú rozdelené do 4 sád. Každá sada je hodnotená 2 bodmi. Platia v nich nasledujúce obmedzenia:

Sada 1 2 3 4
\(1 \leq n \leq\) \(100\) \(5000\) \(100\,000\) \(300\,000\)

Príklad

Input:

6
6 2 1 3 4 5
2 4 6 5 3 1

Output:

5

V jednej z optimálnych konfigurácii sú spojené dvojice stromov \((6, 2), (2, 4), (1, 5), (3, 3)\) a \((5, 1)\).

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.