Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Неспретни Игор се саплео у школи и испустио кутију пуну жица. Пошто је Игор веома посебан, и начин на који су жице пале на под је веома посебан. Под можемо посматрати као координатни систем, где свака тачка на поду има своју координату. Свака жица \(i\) је пала тако да је представљена преко дужи која спаја тачке \((a_i, 1)\) и \((b_i, 2)\), односно, један крај сваке дужи је на прави \(y = 1\), а други на прави \(y = 2\).

Када је Игор ово видео, заборавио је шта је пошао да уради и кренуо да се игра са жицама. Донео је извор струје и жели да види колико најмање жица мора додирнути како би наелектрисао све жице. Жице нису изоловане, па се струја преноси са једне на другу ако се те жице додирују, односно ако се њихове дужи секу.

Но, пошто се никад није бавио такмичарским програмирањем, а има превише жица, није у могућности да то уради сам, па је тражио вашу помоћ.

Опис улаза

У првом реду улаза налази се природан број \(N\) – број жица. У другом реду налази се низ \(N\) природних бројева \(a_1, a_2, ..., a_N\) – координате крајева дужи са праве \(y = 1\). У трећем реду налази се низ \(N\) природних бројева \(b_1, b_2, ..., b_N\) – координате крајева дужи са праве \(y = 2\).

Опис излаза

На излаз исписати минималан број дужи које Игор мора додирнути извором струје како би струја дошла до свих жица.

Ограничења

Подзадаци

  1. (20 поена) \(N \leq 5000\).
  2. (20 поена) Ако додирнувши жицу \(i\) струја стиже до жице \(j\), онда се жице \(i\) и \(j\) додирују.
  3. (20 поена) Коју год жицу Игор додирне струјом, струја ће се проширити на највише још \(5\) жица.
  4. (40 поена) Без додатних ограничења.

Примери

Пример 1

Улаз

4
1 3 7 9
7 1 2 8

Излаз

2

Објашњење

Потребно је додирнути најмање две жице, на пример другу и четврту. Струја са друге жице ће се пренети прво на прву жицу, па одатле и на трећу:

Пример 2

Улаз

6
7 9 8 5 4 6 
9 7 8 2 3 6

Излаз

3