Problem:


Score : 400 points

Problem Statement

Snuke has decided to play a game using cards.
He has a deck consisting of N cards. On the i-th card from the top, an integer A_i is written.

He will perform the operation described below zero or more times, so that the values written on the remaining cards will be pairwise distinct. Find the maximum possible number of remaining cards. Here, N is odd, which guarantees that at least one card can be kept.

Operation: Take out three arbitrary cards from the deck. Among those three cards, eat two: one with the largest value, and another with the smallest value. Then, return the remaining one card to the deck.

Constraints

3 ≦ N ≦ 10^{5}

N is odd.

1 ≦ A_i ≦ 10^{5}

A_i is an integer.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 A_3 ... A_{N}

Output

Print the answer.

Sample Input 1

5
1 2 1 3 7

Sample Output 1

3

One optimal solution is to perform the operation once, taking out two cards with 1 and one card with 2. One card with 1 and another with 2 will be eaten, and the remaining card with 1 will be returned to deck. Then, the values written on the remaining cards in the deck will be pairwise distinct: 1, 3 and 7.

Sample Input 2

15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1

Sample Output 2

7



Sample input:
5
1 2 1 3 7


Sample output:
3

Submission status: Accepted

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
import base64
import subprocess


exe_bin = "e??420s#R400000000000{}h%0RR91@C^U}00000KmY&$00000U@rgw0000000000Kma%Z2>?I<9snHx1^@s61ONa4KmY&$00000KmY&$00000KmY&$00000_yGU_00000_yGU_000002mk;8000000{{R31ONa4I066w00000I066w00000I066w000008~^|S000008~^|S000000RR91000000RR911poj5000000000000000000000000000000Vio`Z00000Vio`Z00000001BW000000RR911^@s6FdYB@00000FdZNO00000FdZNO00000=mG!$00000NCp4^00000001BW000000ssI21^@s6NF4wG00000NF5*m00000NF5*m000005CQ-I000005CQ-I000002mk;8000001ONa41ONa4R004100000R004100000R004100000L;wH)00000L;wH)000001ONa400000P~~)F1ONa4WD@`Y00000WD@`Y00000WD@`Y00000WB>pF00000WB>pF000001ONa400000QRQ@G1^@s6000000000000000000000000000000000000000000000000005C8xG00000Qss1H1ONa4FdYB@00000FdZNO00000FdZNO00000&;kGe00000&;kGe000000RR9100000FKlUIHZ(76WG!rIZgqGqcsMpKHZ(4CZ!R(b1ONa45C8xG0RR91M^04$000000{{R30ssI2000001ONa46aWAK0{{R3M^04$(Idwe?3DA?0bf;Y2+~1B2cVIj0{{R36aWAK0RR911^@s6000mIApjHr6aWAK00000761SMa+U`IC2b5t6_^Y|0000000000000000000000000000009RUCU5&!@I00000000000000000000zySaNA^-pY00000000000000000000;s5{u5&!@I00000000000000000000i2wiq5&!@I00000000000000000000vjG4A5&!@I00000000000000000000f&c&j5&!@I00000000000000000000SOEY45&!@I00000000000000000000q5%K^5&!@I00000000000000000000lmGw#5&!@I00000000000000000000HUR(t5&!@I00000000000000000000&jA1c5&!@I00000000000000000000Z2$lO5&!@I00000000000000000000aRC4T5&!@I000000000000000000009{>OVAOHXW00000000000000000000i2(or5&!@I00000000000000000000*8u<k5&!@I000000000000000000005C8xGAOHXW00000000000000000000I{*LxAOHXW00000000000000000000RR9105&!@I00000000000000000000UI73A5dawgKp`Li000007y$qP00000P5}S_5dawgU?Ly@000005CH%H00000X8`~J5dawgARr(B000005CH%H000000BmVub97{5D=RK@Z!R_fUtec!Z*E_6bYXIIUta)UNmNZ=WMy(?XK8bEWpY$aLu_wuWmI8eY-IpnNmNZ=a%E>}b97~LR82!{Z*FB&VPb4$0AE^8Q*=0KZ*yN_VRL0PNp5L$L@`Bn0AF8ccz9oMWpZ<GZeeU`ba`KPFaTd#WNc7&0AE^8Q)zN@MN(-1Us_XiF*aXcZ*z2VWnpb!X>N06a&$>!Q*<#gV`yP=UvzR|X>@Z*V?{+$Q*<#iVqtS>V_$D`baG{3ZAnyLR4`vfQ#M~vOH(snYye+cQ*<<CZe(mpV^ef7F=J?9a$j_EVQF-8Nn=GtQd4v>Gh$(LX=7h+b98cLVQooNUsNz(MN>9k0AE^DbTKzyUvy}4Z+Bl}VPs!nY;131b^u>mPE&L^X>W61VqtS-G)Zo0bVD&kb^u>mQ*<<AWpZ)=Us`T=Z2(_dQ*<+9X>I^tT2pj1V{dhI0AE^8Q*Uf@MQH$RX<}z%V_$PFb8jv&0AE#ZcWG{9Us7drb!}w;Y-wU+E^}`#HUM8=b97;2YhPn%YhPwzX>0&rUt@S-Utx4*cxiM1UteQ*VP9rxZeeU`dSw7@Wo>P5c4YuxUu<b&V_$Q0VRCd|ZDDC{07pYZUo$Q+07pzoLPK9NE;Il~Oi4mRUotK-E;Rr{SXe<qNnbH8GXO_SNkT(dSYI<PG%h&+M@&gVLs(c}GcGg$000620{{X50ssR50ssO41ONp90ssR51^@y8000L70{{R3000620ssO40ssI2000000RRC2djS9d5C8xGAOHXWP$qc`000L7=>Y%$000000RRF3m;nF)5C8xGFaQ7m6lrM<000C4@c{q;5C8xGbsA|200093`vCv|000000RRI40RR915C8xG00000)30j<000I62Lb>95C8xGiGL{q000F55&{4K5C8xGbSaVu00062AOZjY00000FdZNO000002mk;800000@D2a~00000I2|AW000002mk;800000zzqNZ00000Kph|e000002mk;800000unqtK000002p}K;000002mk;8000002p}K;00000&>tWG000001^@s60ssI20000000000*dHJO000001^@s64gdfE0000000000;2$6W000001^@s65C8xG0000000000=pP^e000001^@s65dZ)H0000000000@E;%m000001^@s65&!@I0000000000_#Yqu000001^@s66951J00000000005Fj7`000000RR913;+NC0000000000ARr(B000001poj5761SM0000000000Kp`Li000001poj56aWAK0000000000U?Ly@000001poj56#xJL0000000000a33H5000002LJ#70RR910000000000cpo4D000002LJ#70{{R30000000000fFB?L000002LJ#71ONa40000000000h#w#T000002LJ#71poj50000000000kRKob000002LJ#71^@s60000000000m>(bj000002LJ#72LJ#70000000000pdTOr000002LJ#72mk;80000000000s2?Bz000002LJ#72><{90000000000upb}*000002LJ#73IG5A0000000000xE~+@000002LJ#73jhEB0000000000z#kw0000002LJ#74FCWD0000000000$R8j8000002LJ#74*&oF0000000000NQ3MMNQ(uH6(9geg}`(I|IkQ-#0bLx0000000000|266qAOQa*>=YmX4<A4P|0U`aAOL6p0002#;Q#;s|0UuSAOL6q0002#(EtDc|0UWKAOL6r0002#!2kdM|0U8CAOL6s0002#u>b%6|0T*4AOL6t0002#p#T5>|0Ti{AOL6u0002#kpKVx|0TK<AOL6v0002#fdBvh|0S{%AOL6w0002#aR2}R|0SvvAOL6x0002#VE_OB|0SXnAOL6y0002#Q2+n`|0S9fAOL6z0002#K>z>$|0R+XAOL6!0002#F#rGm|0RkPAOL2N0000000000K~_OkNR2(^6(9gXR8><*gX|DUjdUagWJrqyB`5#@07!{MBnUCU=p+CC|43tOBm_u>?GJ?H0RR9<xc~qE|NsC0KS(*n4~Gf@002ylEUf?l002yh@8}}`|Nlsd!!f`QA4C8E#{`1_0000;gTMhuImLDGPK_ihNQvD{jWuc&AOK7`;}3+L0001xNQv%DiTCKW{{R0-gT(|%IqY@pOo`~aKL7v#Oo`@5!T175iQh;My}(F=@IOeHNGZZd0n+F-0{{R?gZ)4cjw%5F07!%E2uO`<KuC$-Y5+)y?&#J8002xm<yl^II}aa#00000i**2tRs2YeMf^GPe+}sj0RR9GA4C8ENQuaaPy~xm{78*R{5jTq??{8i1c@+7IqY@JzmQZ60O(5o|Nlsd#Yl~nkW>r+NQvkVA4C8E#{d8T002mXzywG+!gcYBd?W;g|9&EkPya}X*hr0Ziv(s5A4C8ENMi^{gTMrXM2!FeNICFz??{R0G4^II4<Cd800000gE#?$-v3C0zywG+!gcW}_lfwy=pO;cgXaM$$1%Wz{{cviJr@%o01uSFDaPmx{{R0-iO1-5{r~?+iSOv0{r~?+h1+xpNQvL*kp2JvF~CTRTqFo&NHZKIC;$Keb!$k2#1LCuL0myyL0-d1gX{=QiRMU&-)aEpumb=9SX${7|Ns9;iRkG9|NsBLkW>r+G27@>{r~?+iN)y#|Ns9;iSJ2?#ON~p|NlsZ+jIy>iQniY{r~?=iRb8z{r~?-iNx#c=+pfF|L89L|NjpkKmcYg4<Cd800000NR2(J6(9gegX{?CF#Z4kNQ*ro5+DFbjTI^qAOJ{>HH;M?07!$x2<gK7|Nmx?G3`l-(OyW2;z)z!@K97tjRi^t002mh4bubw07#8JJpKRw{}sj&AOQ3aA4C8ENR2)55g-6nNR0*Q5g-6aIrvD4<#ZWHiv^kyAOJ{(z;q2=|KMgW4<Cd800000UBeF_KmcYg4<Cd800000NR2(Q5g-6ajWwzfAOKZJDgH=_<w(K)14xPRNWthoNCC!3(f)K8NQ(tw5g-6ag}`(SUH{-_4<Cd800000UBeF_KmcYg4<Cd800000fIYbsAOHY$FGzzu4-p^$098nd<#Y^4i#<9KAOPrX{Qv*xNdN!;#s!fSAOHbf!w(;T00000^TTEjA4C8ERY-~DUFl~3|NmwWA4C8ENQ3McNR2&J6CeP(0RR91NR4zP2gXDs2MT0Jiv%So0000;i9{p_F~I1-`~Uw)i$o*{WJogvB`5#@0CfdOgTxra=$HHd{|_I400000K~_OkNr}}+iSj{IRY)oNQ%HmQKo5?20RR9^h3!d+{7H%S4}|#u002mhZv;q*^Gqq@L5qAO1WAMK0Z7670*hAsMT-O^NQu};!RS9o0mDeq`$>%qoQnZD$9-uz&<~6@0RR9w*L-O~i994li9{p>i&p$diR(y-@edyWL^;PviQa!NIoC*yLHvDSNR2`G4<A4PNQuEngXjc{Py{*GeDX*+*>+Wl6GVvti&6YRi##Mmi$erRgTn;tzYiaP00000IoEujInWP{$p8QVL5UP3M2SZHM2W&di##Mni$o*@>y2g)A4C8ENQuEnIoWr!4<Cd800000Oo{49iQnk;{{R0-iP}sl;z)z~Kz@Bqh3!a*-VcQi|Ns9;iPK2I`vORfYyL>l{p$%2A4C8ENQ3PGNQ3MML5mEmNQv%h07!}2Oo`{{3;_TDNQLcLUUl6`gYE>7L5l<=Oo{VBiw;PG><COL<1zL~iP}tw=ShR^1VM>L1Zn_C!TJK|)BpegNQ3(XSXzI~TU|k1L0v&!!$FAzBt(e;MT<lv1VM{DB#T!3>B9d1|7I=^AA|q^0001xNICuwgns}406|tvjduh=RY{5UK~zbJ{7E_XRZ~of^K~feR}UWmNjcnf5lD&JOo{hQiRMfx;^@Np|NlsX!vsNzEF?)e-E=XFD?vLfBz)D2Q~XGcL;N|_d<E+;NQuaaPy~xm{78*R{5jQp?};c#gTn+#Io);7TU|k1L0v&!!w(+-^TTEjA4C8ENQu~qDC^v24<Cd800000NR2}OK~+IiNr}}}Q%Q-$L4)N1Nx|$tNdd%3(fmv~<`0ee0000<iSlL-A4C8ENsU4QOpOEpOpOf3O^sOpL5l%OjVzywT>v@5eh5j4>514)iP%j!;6jN6mraSne9ldU?R0TTjX?iMiNZ+1>OV*U!bs8jNjdO-Ktziamqa<ye;MmF4<Cd800000M2i%MNr})%iNZuV(S9CAi4=!SjY9uSjSQDeiNHv~=s!#Wz(~>fNIBMg(?N*|TU|k1L0!XU4<Cd800000Nr~_eA4C8ENR2}NNQuHo!RkLq0m4Yp`b;^(bP`UD42S7(|NsAH4<Cd800000ON~ST0Zfeyhe3-GLWvZINr}MePyhe_4<Cd800000O@-}rt4xgyx9gG*A4C8EL03UmNr~4%RY6otjU_$`AOKZJjV(qBAOKTAiTz25_Dm_|NQ3MMNWuLB=s)-W|44=HbRaR?4<Cd800000Oo{qTiS|T^??L|*+(?7N0Z2LBb?Qii#0XnmL0myyL0&;$!;oe!4<Cd800000^TPlDNQ3MMNQ1-(!vFvP0RRF30UHB5U;qFB3jhEB4EO*4tN;K2-1q<g)Bpeg?Dzlw2m$~AT>Ah2YytoPjQaood;kCdocsU(>;M1&?EC-!kO2Syto{H02mt^9O#c7>SOEY4eE<LdgaQBn?EnA&%mM%a6aWAK000000eVsZ0eBDr8w>{skO2n}6aWAK8~^|S2>Sp3D*ylh00000000006aWAK000000eVsZ0eBDr8w>{skO2SyBme*a8~^|SSoZ(_&;S4c01gmF4j4)g3wH>B06!W#Dl;S^000006aWAKL;wH)0Qdj@2mk;800000000007ytkOTmS$7sQUl^NdN!<07MQTe+mu=K??u?OaK4?cmMzZoc#a)mjD0&080)Kjsivw7>xr(4j_yKM-C{41wjrlg9ZX$4k$qmAVLlpLJkl@4hTfU#>~ymNDeTA28IQU1dRiZ0ssI2Gynhq$N&HU?EL@#D**ri07ecFjRHar7>ol%4j_gEK@KQ`1p>4R4j@4e7(xyZLJkN@3jhEBQ~&?~00961RQmt_wE+MC074EBjsijs7>xr+4j_yKK@KQ}1w;-og9ZaH0S-7x4nR*1I6)3DRSq~+4nR&0I6)3DLkbQkK@K274j4iX5JC<JK??u?8~^|S000000eVnOQUC#X5C@yF3LpR*8w>{skO2SyU;qFBBme*a-1YzeVgdjF1j_&b074EBjsijs7>xr-4j_yKK@KQ}1wjrlg9bznKmx`NNJ$P*Ob$pv4nPA30SXQ<K@KQE4j@7f7(xyZLJkN)3q%e`NDfd&4oE=`KmY&$6aWAK+yMXp==cBsE&u=k080)KUJeKVL;wH)^Z@_>@cjS(WdHyG074EBj{-st7>)x)4j_#LLJla51xOAsh6YFuID-dG4nT4aI6)3DK@KQF4j@7f7(xyZLJkN35C8xGJOTg!82$hM0ssI20000000000|Nj9NC^i59mI0sv(*yv%0}ZnT0Hy>t00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000@D2a~00000zzqNZ00000unqtK000000RR91000000RR91000000RR9100000djS9d000000RR9100000m;nF)000003;+NC00000PznG5000004FCWD00000R1*LI0000082|tP00000FdZNO000008vp<R000005C8xG000008UO$Q00000Kph|e000008~^|S000002mk;800000_5S~F00000m;wL*000001poj500000@B{z=000001^@s600000$N~TW000003IG5A00000ECK)k000003jhEB000007ytkO000006#xJL0000000000000000{{R300000SRWt&000000ssI200000AOQdX000006aWAK000002LJ#7000007XSbN00000FbMzv000002LJ#700000;0FKz000002mk;800000Pyqk{000002><{9000007ytkO000009smFU000002mk;800000`~UxM000000RR9900000{{R1P00000PzL}200000|NsAQ000000{{R300000@c;jB0000090vdZ00000`TzfK000001ONa4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000NF5*m0000000000000000000000000h6(@x00000mI?p>00000rV0Q600000wh90M00000#tHxc00000)(QXs00000<_Z7+00000_6h(1000001`7ZH0000077G9X00000CJO)n00000HVXg%0000000000000000000000000000000000000000000000000000000000000000000000000002p}K;000000000000000M?*t8AShL0b#8QZAU7^GE-)=Kbz*gHbagR)F*q(TG$|lAE;TMN0000000000000000000000000000000000000000000000{{U4I066w000000000000000000000{{X5R0041000000000000000000000{{a6bOHbX000000000000000000000{{d7m;wL*000000000000000000000{{g8$N~TW000000000000000000000{{j9@B{z=000000000000000000000{{mA90vdZ000000000000000000000{{pBPzL}2000000000000000000000{{sC;0FKz000000000000000000000{{vDFbMzv000000000000000000000{{yEPznG5000000000000000000000{{#Fa0&nb000000000000000000000{{&GKnnl>000000000000000000000{{*HPzwM6000000000000000000000{{;IR1*LI000000000000000000000{{>JU=siU000000000000000000000{{^KWD@`Y000000000000000000000{{{L$P)kn000000000000000000000{{~MNEQG9000000000000000000000{|2NFdZNO000000000000000000000{|5OKph|e000000000000000000000{|8PNF5*m000000000000000000000{|BQSRWt&000000000000000000000{|ER03aX$000000000000000000000{|HSARr(B000000000000000000000{|KT000000000000000000000RR911OV~>000000000000000000005&!@I0ssyGP!9kA00000wE+MC00000kN^Mx0ssyGzzqNZ00000E&u=k00000tpET30RR~QaU&oA000000RR9100000yZ`_I1OV~>00000000000000000000#{d8T0ssyGAPxWk000000000000000$p8QV0ssyGU=9EP000000000000000+yDRo0ssyGunqtK000000000000000@&Et;0RR~Qa3df9000000RR91000000RaF20RR;MKph|e000000000000000C;<Qf0ssyG@D2a~000000000000000Gywnr0RR*LFdZNO000000000000000yZ`_I1OV~>00000000000000000000Qvm<~0RR#JL>2%5000000000000000000001OV~>00000000000000000000VF3UD000pHWD@`Y000000000000000bO8VW0RR>NNF5*m000000000000000eE|Rf000yKKph|e000000000000000jsXAw000yKFdZNO000000000000000p#cB@0RR^OSRWt&000000000000000w*deE5C9ke7$6`3000000000000000Wdr~KAOIKu03aX$000000000000000z5xIL5daVXU=siU000001ONa400000%>e)a5&!@I00000000000000000000^8o+=A^;8m5D@?X00000mjD0&00000WdZ;IA^-pY00000000000000000000fdT*k5&#YWPzwM600000VgdjF00000h5`Tp5&!@I00000000000000000000&H?}cA^;8mun_<N00000D**ri00000MFRi;5ds(h2p}K;000000000000000QUd@05&!@I00000000000000000000p8x;=5&#YW01p5F00000NdN!<00000Y6AcOAp#fx5Fj7`000002mk;800000JOuy%5&#bXR1*LI000000000000000h64Zq5&!@I00000000000000000000paTE^5&!@I00000000000000000000X#@ZO5&#YW@C^U}00000D*ylh00000v;zPD5&!@I00000000000000000000#{&QW5&!@I00000000000000000000s{{Z55&#PTPznG5000000000000000;{yNy5ds(h7$6`3000000000000000?*jk;5&!@I00000000000000000000OauS`5dawgARr(B000005CH%H00000V*~&I5C9ke03aX$000000000000000i2(or5C9nfcq1SH000000000000000a0CDV5C9nf7$6`3000000000000000d;|ah5&!@I00000000000000000000p#%T`5&#YW;1U1;00000WdHyG00000u>=4B5&!@I00000000000000000000#smNW5&!@I00000000000000000000=L7%%5&!@I00000000000000000000{saI3AOHXW000000000000000000008U+9V5&!@I00000000000000000000G6ett5&#YWP!j+E000000ssI200000LInT-5dawgKp`Li000007y$qP00000SOow85&!@I00000000000000000000cLe|dAOHXW00000000000000000000h6MlsAOHXW00000000000000000000palQ`5dawgU?Ly@000005CH%H00000w*>$I5&!@I0000000000000000000007PFyVRB?&MPYPhaxP<VZ~$LgQ*<#lUtei%baHQVZ*p{BY;SLHNlrOmUuSN0Ut@T9F*jddZf|mJVQgP%bY*g3bZ>G=P-#<iHg;uWbZ>G=X;WcIX+=dvMQlz}FkdxaUvF@8F*RRFbY*g1Y-MwEUukq@az#aUR9{m$UsNz(R54#JX>)R6E;BR$Uq?(&LP1PlUvqV0UrAqIS~+B8Vs&R<Z*_Eb0AE^DbWAv3Uukb?ZfSG?V{&wJbaiHCE@J>>WpZU_X>)XCa$j_9Ut?@<Ze?=-UteTzUuSG@Vqt7wWOQ$Gb6;U~cmQK>ZE$R5bY)~NH#Rvq0AF8ZZ(nC@Z(?C=Uu1M|a&uo{b$DN9X>Ms>VRCX|d0%C2baHtBW^!R|WnW}<ZEbk~UteZ&VQpn!WOZ$Ad0%O6X>?y<a&lpLUuAA|a(Mt>Uq(_vO+{ZtPDEc{0AF86PE}t;NMA-$K}|(pNJLTqUqo3>K}|_R0AF8eZfSI1VRCX|d0%C2WB^}ZX>MtBUtw}`VR>J3bYXII0AEK;PeMUVUr$CxQ$<u?R6#;aMPC44Wn^J=VE|uAPhWF%WNB_+b#rB80AE^DbTKzyUvy}4Z+Bl}VPs!nY;131c0fQ!Oi4mRSXf^(E;ImNT2pi}HeX+9ZgXXFbZKvHUvqDAbV*J*Utec#bzft6criC$Uv6)5ZDDL*X>?_BVRUbDNl<B1bT)QnV{~tFNoiAINohqzMMX|iFkdxaUvF@8F*RRFbY*g1Y-MwEUukq@az#aUR9{m$UsNz(0AF8Ycwt{=X>MU`X?kTqKu1hTLPK9NE;24P0BvDuZUA3eQ*<<CZe(mpV^ef7F=J?9a$j_EVQF-8Nn=GtQd4v>Gh$(LX=7h+b98cLVQooNUsNz(MN>9kKtM-KNkT(dSYI<PGyq>(Q*<#iUteKlYISpTUub1va7j)%Utec#bzft6criC$Uv6)5ZDDL*X>?_BVRUbDNl<B1bT)QnV{~tFNoiAINohqzMMZ3BPE#;nHD6zEaC0#=UrBUja$js^b8}y5bY*fyMRrtQR4`vtL0?ocUsN(*0AF8Zb8la0VQyq>WdL7VPE%=eb45~VKtM-KNkT(dSYI<PGyp_bE^=jNE?-|~cz9oMWpZ<GZeeU`ba`KPFaTd)V|Za-VRU79X>>q9M@&gVLtip3GA=a$Us_~rP<B8-M@&gVLs(c}GcGg$Us`T=Z9qUrOi4mRSXf^(E;ImNUvqR}V{2byXlq|)VQFkYKu1hTLPK9NE;ImNUsO#)UqwztUta)UT2pi}HeX+Fb98cLVQpV&ZgXXFbV*}VbTKhwXkl_+baG*7baP2#MMY9mbTKnxVRLC?UvG1Ca%Ev{NmO4{FkeMeHeXOnQ!`&|KtM-KNkT(dSYI<PG%h&+Us_XiG-GddbU;8yOi4mRSXf^(E;ImNUu0o)VPA7}VRCc;UteN#b6<0GVRCc;Us_I6bU0~mb6;X%b7eG1ZfSHwF-3MjKu1hTLPJ<sUo$Q=0AF8hX<}nvV{>(1X>MtB0BvP$ZEtpEKtM-KNkT(kGA=SMH2_~<XLxvDaAk6HZ*F01X>@sCb}&FdLs(crLP=jSE;9gMT251MY;#3vKtM-KNkT(dSYI<PGyq>oR83!GWpZU_X>)XCa#T%2Y;SI5RAFLlWdL7QZg**JWM5Kcb9HTHKtM-BLtis4FaTd)Y-wU+Ut@E1UuJ1;X#ihZQ*<+9X>LG3M@&gVLs(c}GcGg$Uter#Vq;%(bYXIIUu|J&Za_dsOi4mRUotK-E;RsOUuSJ^ZeMeBVRCd|UjSc8R83!UWoKz~bY*f>O+##NZe>(qVr*pqUs_XiG-G9QazH>wOi4mRSXf^(E;ImNT251RIB9QlUt(c%Wi&}{X>>#}MRq_yM@&gVLs(c}GcGg$04{TRZFFH`04{TMa&%#004{TAb98caVPXI-X>N37a&Q1HZf|sDE<r*`Ep%aL04{ECbY(7QZgnnVb!lv5Eoo!`E@y6aE@)wMXaFu`d2VxgZ2&H0d2VxbasV!8ZgnnpWpZ<AZ*BlCXKr;ac4cyNX>V>{asV!JWo%(CWO;4?E^=jTVJ>iNbO0`CZfSG?E^usgE@y9a04{W8cys_RW@&C|04{QGWMOn+04`-{UuJS)ZDn6*WO4v5WoTb!a$#*{04`@^V_#)>V`Xr3Uvyz&Y-Ip0X>MtBUtw}`VR-;9W@&C|Utw}`VR-;9WO;63ZE0fwE@WYJVE`^-b8`SLV{dJ3Wo~o;00000000000000000000000000000000000000000000000000000000000000000000000000000000000008vp<R0RR910ssI200000I066w00000I066w000008~^|S0000000000000000RR91000000000000000BLDyZ2LJ#70ssI200000R004100000R004100000AOHXW0000000000000001ONa4000000000000000F#rGn2LJ#70ssI200000bOHbX00000bOHbX00000Bme*a0000000000000001ONa4000000000000000L;wH)_W%EH0ssI200000m;wL*00000m;wL*00000FaQ7m000001poj5000002mk;8000000000000000P5=M^3jhEB0ssI200000$N~TW00000$N~TW00000C;|Wg000001^@s60RR912mk;8000007ytkO00000RsaA10{{R30ssI200000@B{z=00000@B{z=00000ECK)k0000000000000000RR91000000000000000UH||9|NsAQ0ssI20000090vdZ0000090vdZ00000E&u=k000001poj5000000ssI2000000ssI200000YXATM{{R1P0ssI200000PzL}200000PzL}200000kN^Mx000001^@s60{{R32mk;8000000000000000dH?_b1ONa40ssI200000;0FKz00000;0FKz00000Pyqk{000001poj5000002mk;8000007ytkO00000ga7~l1ONa4LI3~&00000FbMzv00000FbMzv00000AOQdX000001poj57XSbN2mk;8000007ytkO00000jsO4v0RR911^@s600000PznG500000PznG5000007XSbN0000000000000001ONa4000000000000000i2wiq0RR911^@s600000a0&nb00000a0&nb00000&;S4c0000000000000005C8xG000005C8xG00000lmGw#0RR911^@s600000Knnl>00000Knnl>000002mk;80000000000000002mk;8000002mk;800000od5s;0RR911^@s600000PzwM600000PzwM6000000tf&A0000000000000005C8xG000000000000000qW}N^0RR911^@s600000R1*LI00000R1*LI000002><{90000000000000001ONa4000000000000000sQ>@~0RR915&!@I00000U=siU00000U=siU000001ONa40000000000000001ONa4000001ONa400000u>b%70RR910ssI200000WD@`Y00000WD@`Y00000WB>pF0000000000000001ONa4000000000000000zW@LL0RR910ssI200000$P)kn00000$P)kn00000fC2yj0000000000000002mk;8000000000000000$p8QV0RR910ssI200000NEQG900000NEQG9000008UO$Q0000000000000000RR91000000000000000+W-In4gdfE0{{R300000FdZNO00000FdYB@000005C8xG0000000000000002mk;8000002mk;800000=Kufz4*&oF0{{R300000Kph|e00000Kpg-8000002mk;80000000000000002mk;8000002mk;800000^8f$<1^@s60{{R300000NF5*m00000NF4wG000005CQ-I000001^@s6000002mk;8000005C8xG00000m;e9(0RR910{{R300000SRWt&00000SRViY00000r~m)}0000000000000002mk;8000002mk;800000`~Uy|0RR910{{R30000003aX$0000003ZMW000007ytkO0000000000000002mk;80000000000000000s#O32mk;80{{R300000ARr(B000007$5)u00000SOWk6000000000000000AOHXW0000000000000002LS*80RR91FaQ7m0000000000000007$5)u00000DF6Tf0000000000000000RR91000000RR91000000RR910ssI200000000000000000000NFV?J00000C<p)m000008~^|SF8}}l2mk;8000007ytkO000002><{90{{R300000000000000000000a3}x(00000+ywvt0000000000000000RR910000000000000005dZ)H0{{R300000000000000000000OfCQb000005CH%H0000000000000000RR91000000000000000"

open("./kyomu", 'wb').write(base64.b85decode(exe_bin))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
n = int(input())
A = set(list(map(int,input().split())))

if len(A) % 2 == 0:
  print(len(A)-1)
else:
  print(len(A))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    A = LI()
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    # print(counter)

    odd = 0
    ans = N
    for key, val in counter.items():
        if val > 1:
            c = val - 1
            # print(val, c, c // 2)
            if c % 2 == 1:
                odd += 1
            ans -= (c - c % 2)
    # print(ans, odd)
    ans = ans - (odd // 2) * 2 - (odd % 2) * 2
    print(ans)

            

    

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    A = LI()
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    # print(counter)

    odd = 0
    ans = N
    for key, val in counter.items():
        if val > 1:
            c = val - 1
            # print(val, c, c // 2)
            if c % 2 == 1:
                odd += 1
            ans -= (c // 2) * 2
    # print(ans, odd)
    ans = ans - (odd // 2) * 2 - (odd % 2) * 2
    print(ans)

            

    

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = max(A)

B = [0]*(M+1)
for i in range (0, N):
	B[A[i]]+=1

for i in range (0, M+1):
	if B[i] > 2:
		B[i] = 2-(B[i]%2)
        
count = 0

for i in range (0, M+1):
	if B[i] == 2:
		B[i] = 1
		count+=1
        
print(sum(B)-(count%2))

Submission status: Accepted

Solution code:
from collections import Counter

n=int(input())
a=list(map(int,input().split()))

c=Counter(a)

q=0
for v in c.values():
  if v>=2:
    q+=v-1

ans=len(c.keys())
if q%2==0:
  print(ans)
else:
  print(ans-1)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

n=int(input())
a=lnii()

c=Counter(a)

q=0
for v in c.values():
  if v>=2:
    q+=v-1

ans=len(c.keys())
if q%2==0:
  print(ans)
else:
  print(ans-1)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))

# N 奇数
M=N-len(set(A))

if M%2==0:
    print(N-M)
else:
    print(N-M-1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
memo = {}
for a in A:
    if a in memo:
        memo[a] += 1
    else:
        memo[a] = 1
memo_sorted = sorted(memo.items(), key=lambda x:-x[1])
memo = []
for a,b in memo_sorted:
    memo.append([a,b])

for key,val in enumerate(memo):
    val_1, val_2 = val
    if val_2 <= 1:
        continue
    else:
        if val_2%2 == 1:
            memo[key][1] = 1
        elif val_2%2 == 0:
            if key < len(memo)-1:
                memo[key+1][1] -= 1
                memo[key][1] = 1
            else:
                memo[key][1] = 0
ans = 0
for a,b in memo:
    ans += b
print(ans)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    from collections import Counter
    n = input_int()
    A = input_int_list()
    A_cnt = Counter(A).most_common()
    A_cnt = [list(a) for a in A_cnt]
    cnt = 0
    for i in range(len(A_cnt)):
        if A_cnt[i][1] > 2:
            if A_cnt[i][1] % 2 == 1:
                cnt += A_cnt[i][1] // 2
                A_cnt[i][1] = 1
            elif A_cnt[i][1] % 2 == 0:
                cnt += (A_cnt[i][1] // 2) - 1
                A_cnt[i][1] = 2
        if A_cnt[i][1] == 2:
            if i + 1 < len(A_cnt):
                A_cnt[i + 1][1] -= 1
            A_cnt[i][1] = 1
            cnt += 1
    print(n - cnt * 2)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
A = LI()
B = [0]*(10**5+1)
for a in A:
    B[a] += 1

print(sum(B[i] != 0 for i in range(10**5+1))-(sum(max(0,B[i]-1) for i in range(10**5+1)) % 2))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))

k = len(set(A))
if k % 2:
    print(k)
else:
    print(k-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[2]:


import collections


# In[13]:


N = int(input())
A = list(map(int, input().split()))


# In[14]:


mycnt = collections.Counter(A)
mylist = mycnt.keys()
length = len(mylist)
if length%2 == 0:
    print(length-1)
else:
    print(length)


# In[ ]:

Submission status: Accepted

Solution code:
import sys
from collections import Counter

input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

counter = Counter(A)
# print(counter)
ans = 0
tmp = 0
for n, count in counter.items():
    r = (count - 1) // 2
    count -= 1 + 2*r
    ans += 2*r
    if count == 1:
        tmp += 1

print(N - ans - tmp - tmp % 2)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
C = {}
for i in range(N):
    a = A[i]
    if a not in C:
        C[a] = 0
    C[a] += 1
n = len(C)
if (N-n)%2==0:
    print(n)
else:
    print(n-1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
A = LI()
B = sorted(set(A))
d = {}
for b in B:
    d[b] = 0
for a in A:
    d[a] += 1

C = [d[b] for b in B]

ans = len(B)
x = sum(c-1 for c in C)
if x % 2 == 1:
    ans -= 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
count = Counter(A)
cnt = 0
for val in count.values():
    if val % 2 == 0:
        cnt += 1
ans = len(set(A)) - cnt % 2
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import Counter
A=list(Counter(A).values())
ans=A.count(1)
l=[i-1 for i in A if i>1]
print(ans+len(l)) if sum(l)%2==0 else print(ans+len(l)-1)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N,A=ilint()
C=counter()
for a in A:
    C.add(a)
ans=0
for k in C:
    ans+=max(0,C[k]-1)
print(N-2*((ans-1)//2+1))

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

cnt = Counter(A)

x = N-len(cnt.values())

print(N-(x+1)//2*2)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = len(set(a))
if ans % 2 == 0:
    print(ans-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = set(A)
    if len(A) % 2 == 0:
        print(len(A) - 1)
    else:
        print(len(A))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))

cnt = [0] * max(A)

for i in range(len(A)):
    cnt[A[i]-1] += 1

ok = 0
ans = 0

for i in range(len(cnt)):
    if cnt[i] == 0:
        continue
    ans += 1
    if cnt[i] % 2 == 0:
        ok = 1 - ok

if ok == 1:
    ans -= 1

print(ans)