Според многу луѓе, 2020 година е една од најлошите – поради пандемијата на вирусот КОВИД-19, забраните за собирање, губењето на работни места, итн. Како и останатите луѓе, Марија поминува голем дел од оваа година пред телевизија, гледајќи вести. Интересно, таа забележала дека голем број од вестите кои се објавуваат на телевизија се повторуваат – на пример, објавување на информации за тестирање на вакцина, па потоа по неколку денови, слична таква информација за тестирање на вакцина, итн.

За оваа задача, ќе претпоставиме дека информациите кои се објавуваат на вести можат да се претстават со цели броеви, и за две објавени информации велиме дека се исти доколку тие се претставени со ист број. Нека кажеме дека една информација е “значајна” доколку таа се објавила точно двапати. На пример, во [1, 3, 1, 3, 2, 1], информацијата означена со 3 е “значајна”, информацијата означена со 2 не е значајна бидејќи се појавува еднаш, додека информацијата означена со 1 не е значајна бидејќи таа се објавила повеќе од двапати па може да се смета за стандардна или секојдневна информација.

Марија сега се прашува што би се случило доколку таа разгледува само еден последователен дел од почетната низа со информации? На пример, што доколку од низата дадена погоре ги исфрлиме последните два елементи по што ќе добиеме [1, 3, 1, 3]? Во овој случај, имаме две “значајни” информации (1 и 3), наместо една значајна информација (3) во оригиналната низа.

За дадена почетна низа од информации X, одберете последователен дел од елементи Y од почетната низа, така што бројот на значајни информации во Y ќе биде најголем можен. Последователниот дел од елементи може да почне на кое било место во низата X – т.е. не мора да се почне од почетокот како во примерот даден погоре.

Влез

Во првиот ред е запишан еден цел број N (1 <= N <= 100 000), кој го означува бројот на информации. Во вториот ред се запишани N цели броеви Xi (0 <= Xi <= 1000000000) кои ги дефинираат информациите, според редоследот по кој тие се објавувани на вести.

Забелешка: Во тест случаи кои носат најмалку 20% од поените, бројот N ќе биде помал или еднаков на 100. Во други тест случаи кои носат најмалку 30% од поените, бројот N ќе биде помал или еднаков на 10000.

Излез

Во еден ред се запишува бараниот максимален број на “значајни” информации.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
6
1 3 1 3 2 1

излез
2

влез
12
5 5 1 3 9 9 9 1 3 5 2 1

излез
3

Објаснување за првиот тест пример: дадено во текстот на задачата.

Објаснување за вториот тест пример: Ако ги разгледаме последователните елементи почнувајќи од вториот па се до десеттиот, имаме [5, 1, 3, 9, 9, 9, 1, 3, 5], каде што значајни информации се 1, 3 и 5. Како што е дефинирано во текстот на задачата, информацијата означена со 9 не е значајна бидејќи се појавува повеќе од двапати.