Gudrinieku ciemā ir N mājas, kuras ir izvietotas vienā rindā. Šo N māju īpašnieki ir ļoti turīgi un principiāli ļaudis. Viņi ir gatavi maksāt par ceļu izbūvi starp mājām, bet ar vienu nosacījumu – ceļiem ir jātiek izbūvētiem maksimāli daudz pēc skaita starp mājām pēc principa, ka tie nedrīkst krustoties. Iemesls – tā esot skaistāk. Ja eksistē ceļi (a, b) un (u, v), tiek uzskatīts, ka šie ceļi nekrustojas, ja a ≤ u un b ≥ v vai a ≥ u un b ≤ v. Celtniecības firmā ceļu izbūves tāmē ir jāuzrāda ceļu skaits. Tavs uzdevums ir aprēķināt šo maksimālo ceļu skaitu, ievērojot dotos principus.

Ievaddatu pirmajā rindā ir dots viens vesels skaitlis N, māju skaits (1 ≤ N ≤ 10⁹).

Izvaddatos ir jāizvada viens skaitlis – kāds ir maksimālais nekrustojošos ceļu skaitu, ko var izbūvēt starp mājām.

Starp divām mājām drīkst būt tikai viens ceļš. Piemēram: