Ţirbi a scris pe o foaie de hârtie următorul şir de numere: 1,2,3,4,...,2N. El modifică şirul în felul următor: p(1), p(2N), p(2), p(2N­1), p(3), p(2N­2), p(4), p(2N-3),...,p(N­1), p(N+2), p(N), p(N+1), unde p(i) este numărul de la poziţia i.

Cerinţă

Dându-se N, să se afle numărul minim de modificări care trebuie aplicate şirului pentru a se ajunge din nou la şirul iniţial.

Date de intrare

Fişierul de intrare oneton.in conţine un singur număr natural N pe prima linie.

Date de ieşire

Fişierul de ieşire oneton.out conţine o singură linie pe care va fi scris numărul de modificări care trebuie aplicate şirului.

Restricţii

• 1 <= N <= 2 000 000
• Atenţie: şirul este format din toate numerele de la 1 până la 2N.
• Pentru 30% din teste N < 1 000

Exemplu

oneton.in	oneton.out	Explicaţie
4	4	Pas 0: 1 2 3 4 5 6 7 8 (şirul iniţial) Pas 1: 1 8 2 7 3 6 4 5 Pas 2: 1 5 8 4 2 6 7 3 Pas 3: 1 3 5 7 8 6 4 2 Pas 4: 1 2 3 4 5 6 7 8 (şirul iniţial)

stud. Cosmin-Mihai Tutunaru

Universitatea Babeş-Bolyai

cosmin@tutunaru.ro