sala

Cerință

Preşedintele unui Concurs de Informatică doreşte ca la festivitatea de încheiere să fie o atmosferă plăcută. Pentru acest lucru el vrea să aşeze participanţii pe $n$ rânduri după anumite reguli. Aceaste reguli sunt:

• pe primul rând al sălii aşează una lângă alta $n$ persoane.
• pe rândurile următoare aşeazarea pe poziţia $i$ (numerotarea se face de la stânga la dreapta) este condiţionată de aşezarea persoanelor de pe rândul anterior, adică dacă pe rândul din faţă pe poziţiile $i$ şi $i+1$ stau fie numai băieţi fie numai fete, atunci se va aşeza o fată, iar dacă pe aceste poziţii stau persoane de sex opus se va aşeza un băiat.

Conform acestei reguli pe rândul cu numărul de ordine $i$ $(i \in{1, 2, \dots, n})$ se vor aşeza $n-i+1$ persoane.

Pentru $n$ dat se cere să se determine numărul maxim de băieţi ce pot lua loc în sală, astfel încât să se respecte regulile anterioare.

Date de intrare

În fişierul text sala.in pe prima linie se află numărul de cifre ale lui $n$, iar pe linia a doua se află cifrele numărului $n$ separate între ele prin câte un spaţiu.

Date de ieșire

În fişierul text sala.out pe prima linie se va afişa numărul din cerinţă.

Restricții și precizări

• $1 \leq n \leq 10^{101}$
• Pentru 30% din teste, $n < 100$
• Pentru 70% din teste, $n < 30 \ 000$

Exemplul 1

sala.in

1
5

sala.out

10

Exemplul 2

sala.in

2
1 3

sala.out

61