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

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

• Најпре се бројеви у низу \(A\) сортирају у неопадајући поредак и тако се добије нови низ \(A' = [a'_1, a'_2, ..., a'_k]\).
• Слично се бројеви у низу \(B\) сортирају у неопадајући поредак како би се добио нови низ \(B' = [b'_1, b'_2, ..., b'_k]\).
• На крају се бројеви у низовима упоређују један по један, тј. број \(a'_i\) се упоређује са \(b'_i\) (где \(1 <= i <= k\)). Са \(R_1\) означимо број пута где је \(a'_i > b'_i\), а са \(R_2\) број пута где је \(a'_i < b'_i\). Број поена које први играч освоји је баш \(R_1\), а \(R_2\) представља број поена другог играча.

Нпр. претпоставимо да је \(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.

• Уколико је \(k = 1\), онда имамо \(A = [x_1] = [2], B = [x_2] = [4]\), тј. \(A' = [2], B' = [4]\) и овде имамо да је \(R_1 = 0\).
• Уколико је \(k = 2\), онда имамо \(A = [x_1, x_2] = [2, 4], B = [x_3, x_4] = [6, 1]\), tj. \(A' = [2, 4], B' = [1, 6]\) и овде имамо да је \(R_1 = 1\).
• Уколико је \(k = 3\), онда имамо \(A = [x_1, x_2, x_3] = [2, 4, 6], B = [x_4, x_5, x_6] = [1, 5, 3]\), tj. \(A' = [2, 4, 6], B' = [1, 3, 5]\) и овде имамо да је \(R_1 = 3\).
• Уколико је \(k = 4\), онда имамо \(A = [x_1, x_2, x_3, x_4] = [2, 4, 6, 1], B = [x_5, x_6, x_7, x_8] = [5, 3, 5, 2]\), tj. \(A' = [1, 2, 4, 6], B' = [2, 3, 5, 5]\) и овде имамо да је \(R_1 = 1\).

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

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

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

• \(1 \leq x_1, x_2, ..., x_{2 \cdot N} \leq 6\)

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

• Подзадатак 1 [21 поен]: \(1 \leq N \leq 100\).
• Подзадатак 2 [31 поен]: \(1 \leq N \leq 5000\).
• Подзадатак 3 [48 поен]: \(1 \leq N \leq 1000000\)