“Ajuns în fruntea neamului său, care era istovit de războaie dese, Burebista l-a înălțat atât de mult prin exerciții, abținere de la vin și ascultare de porunci, încât, în câțiva ani, a întemeiat o mare stăpânire.” (Strabon – Geografia)

Burebista tocmai a primit printre oștenii săi daci și pe aliații săi, bastarnii. Cu toții s-au aliniat într-un șir lung în fața regelui, dacii fiind etichetați cu 1, iar bastarnii cu 2.

Cerințe

Dacă răspundeți corect la două cerințe, marele rege Burebista vă va primi în oastea sa invincibilă:
1. Câți oșteni daci se află în șir? Mai simplu spus, câte valori de 1 se află în șir?
2. Care este lungimea maximă a unei secvențe de oșteni formată fie din daci, fie din bastarni? Deci aflați lungimea maximă a unei secvențe din șir formată doar din valori de 1, sau doar din valori de 2.

Date de intrare

Fișierul de intrare burebista.in conține pe prima linie două numere naturale nenule C și n, separate printr-un singur spațiu. Pe următoarea linie, separate prin câte un spațiu, se află un șir de n numere naturale din mulțimea {1, 2} , unde 1 înseamnă oștean dac, iar 2 oștean bastarn.

Date de ieșire

Fișierul de ieșire burebista.out va conține pe prima linie răspunsul determinat pentru cerința C:

• Pentru C = 1, prima linie conține un singur număr natural reprezentând numărul de daci din șir.
• Pentru C = 2, prima linie conține un singur număr natural reprezentând lungimea maximă a unei secvențe din șir formată doar din valori de 1, sau doar din valori de 2.

Restricții și precizări

• C ∈ {1, 2}
• 3 ≤ n ≤ 100.000
• Pentru 60 de puncte, C = 1
• Pentru 40 de puncte, C = 2

Exemplul 1:

burebista.in

1 8
2 1 1 2 1 2 1 1

burebista.out

5

Explicație

Cerința este 1. Trebuie să aflăm câți de 1 sunt în șir, iar răspunsul este 5

Exemplul 2:

burebista.in

2 10
1 2 2 2 1 1 1 1 2 1

burebista.out

4

Explicație

Cerința este 2. Cea mai lungă secvență cu proprietatea cerută este formată din \\@4@ valori de 1 aflate pe poziții consecutive în șirul dat.