romania

Romania

== include(page="template/taskheader" task_id="romania") ==

Poveste şi cerinţă...

Fie $P$ un poligon convex regulat cu $N$ vârfuri numerotate în ordine trigonometrică. Dându-se un şir $grad[i] = numărul de diagonale care au un capăt în vârful cu numărul i$, voi trebuie să determinaţi o mulţime de diagonale ale poligonului care să satisfacă acest şir iar oricare două dintre acestea să *nu* se intersecteze decât în capete. Reamintim că se numeşte diagonală a poligonului orice segment care uneşte două vârfuri neconsecutive ale acestuia.

h2. Date de intrare

Fişierul de intrare $romania.in$ ...

Fişierul de intrare $romania.in$ va conţine pe prima sa linie $N$, semnificând numărul de vârfuri ale poligonului.

h2. Date de ieşire

În fişierul de ieşire $romania.out$ ...

În fişierul de ieşire $romania.out$ va conţine $SUM$ linii, unde $SUM$ este suma tuturor valorilor din $grad[]$. Fiecare dintre aceste linii va conţine o pereche $x y$, semnificând faptul că includeţi diagonala dintre vârfurile $x$ şi $y$ în soluţia voastră.

h2. Restricţii

* $1 ≤ N ≤ 100.000$

* $3 ≤ N ≤ 100.000$

* Pentru teste in valoare de *40* de puncte $N ≤ 1.500$
h2. Exemplu