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

Пошто је добио дозволу за убијање, добро познати агент Бонд, Џејмс Бонд, се упутио у, нама суседну, Црну Гору како би спасио свет. Он је сазнао да се озлоглашени Ле Шифр упутио у казино како би учествовао у турниру са великим улогом у игри Ројал. Како би осујетили планове Ле Шифра и натерали га да се преда, МИ6 планира да убаци Бонда у турнир, верујући да баш он може да победи. Као што то обично бива, до финала су стигли баш Бонд и Ле Шифр.

Ројал је веома једноставна игра. На почетку игре се одреди број \(k\). Потом први играч баца шестострану коцкицу (свака страна коцкице има урезан број од 1 до 6) \(k\) пута и забележе се бројеви на којима коцкица стане приликом сваког бацања. Означимо добијене бројеве са \(A = [a_1, a_2, ..., a_k]\). Затим други играч баца исту коцкицу \(k\) пута и забележи бројеве које добије. Означимо добијене бројеве са \(B = [b_1, b_2, ..., b_k]\). После бацања коцкица следи упоређивање низова \(A\) и \(B\) и то се ради на следећи начин:

Нпр. претпоставимо да је \(k = 5\) и да први играч приликом бацања коцкице добија бројеве \(A = [6, 4, 1, 4, 3]\), а други играч добија бројеве \(B = [1, 5, 3, 2, 5]\). По сортирању ових низова добијамо низове \(A' = [1, 3, 4, 4, 6]\) и \(B' = [1, 2, 3, 5, 5]\). Упоређивањем бројева ова два низа имамо: \(1 = 1\), \(3 > 2\), \(4 > 3\), \(4 < 5\) и \(6 > 5\), тј. \(R_1 = 3\) и \(R_2 = 1\).

Бонд је сазнао да ће у финалу да се користи специјална коцкица за коју може да предвиди на којим бројевима ће да стане за првих \(2 \cdot N\) бацања, тј. у првих \(2 \cdot N\) бацања, коцкица ће да падне на бројеве \(X = [x_1, x_2, ..., x_{2 \cdot N}]\) редом. Зна се да ће Бонд да буде први играч и још има право да одабере број \(k\) који представља број бацања коцкице сваког играча у игри. Међутим, мора да важи да укупан број бацања коцкице не сме бити већи од \(2 \cdot N\), тј. \(1 <= k <= N\).

Ваш задатак је да помогнете Бонду да одабере њему најповољније \(k\), тј. такво \(k\) где ће освојити највише поена.

Опис улаза

У првој линији стандардног улаза се налази природан број \(N\) који означава максималан број бацања коцкице. У следећем реду се налази \(2 \cdot N\) целих бројева \(x_1, x_2, ..., x_{2 \cdot N}\) који представљају вредности на које ће коцкица да падне у првих \(2 \cdot N\) бацања, редом (у првом бацању коцкица ће да падне на број \(x_1\), у другом на \(x_2\), итд.).

Опис излаза

На стандарни излаз је потребно исписати један цео број, \(R_1\), који представља максималан број поена које Бонд може да освоји.

Примери

<div class="panel panel-default">
    <div class="panel-heading">
        <span class="pull-left" style="width: 48%;">Ulaz</span>
        <span style="padding-left: 15px;">Izlaz</span>
    </div>
    <div class="panel-body">
        <span class="pull-left exampleinput">
            4<br/>                                          
            2 4 6 1 5 3 5 2
        </span>
        <span class="exampleoutput">
            3
        </span>
    </div>
</div>
<div class="panel panel-default">
    <div class="panel-heading">
        <span class="pull-left" style="width: 48%;">Ulaz</span>
        <span style="padding-left: 15px;">Izlaz</span>
    </div>
    <div class="panel-body">
        <span class="pull-left exampleinput">
            2<br/>
            1 1 2 2
        </span>
        <span class="exampleoutput">
            0
        </span>
    </div>
</div>

Објашњење примера

У овом тест примеру, могуће вредности за \(k\) су 1, 2, 3 и 4.

Дакле, највећи број поена које Бонд може да освоји је 3.

У другом тест примеру, које год \(k\) Бонд да одабере, имаће 0 поена.

Ограничења и подзадаци

Постоје 3 подзадатка, у којима додатно важи: