Regele Gefghev s-a gândit să viziteze o ţară în care se întâmplă multe minuni, Ţara Minunilor. Această ţară este alcătuită din $N$ oraşe, numerotate de la $1$ la $N$. Între oraşele $i$ şi $i+1$ $(1 &le; i < N)$ există o stradă modernă pe care se poate circula doar de la oraşul $i$ la oraşul $i+1$. Fiind un tip isteţ, Gefghev şi-a dat seama că el poate ajunge de la orice oraş $i$ la un oraş $j (j > i)$ mergând în total pe $j-i$ străzi. Tronomir, angajat al direcţiei de întreţinere a drumurilor, a pus la cale un plan de construcţie a $M$ noi străzi pentru a-i fi mai uşor lui Gefghev să călătorească. Străzile vor fi construite rând pe rând, în M zile consecutive, în ziua i fiind construită cea de-a i-a stradă. O stradă va fi construită de la oraşul $a$ la oraşul $b$ $(1 &le; a < b – 1 < N)$ şi pe această stradă se va putea circula doar de la oraşul a către oraşul b. Fiind un tip preocupat de călătorii, Gefghev se gândeşte acum să afle, după fiecare stradă construită, între care oraşe poate ajunge acum mai repede decât putea înainte de construcţia străzii. Altfel spus, el vrea să ştie câte perechi de oraşe $(x, y)$ $(1 &le; x < y &le; N)$ şi-au schimbat distanţa minimă dintre ele. Distanţa minimă dintre două oraşe $x$ şi $y$ este numărul minim de străzi care trebuie să fie parcurse pentru a ajunge din oraşul $x$ în oraşul $y$.

h2. Cerinta

h2. Cerinţă

Scrieţi un program care determină pentru regele Gefghev, după fiecare stradă construită, numărul de perechi de oraşe $(x,y)$ $(1 &le; x < y &le; N)$ pentru care distanţa minimă de la $x$ la $y$ s-a modificat după construirea străzii respective.

h3. Explicaţie

Există $8$ oraşe. Se vor construi $3$ noi străzi. După construcţia străzii $2 4$, se vor modifica distanţele dintre următoarele perechi de oraşe: $(1 4), (1 5), (1 6), (1 7), (1 8), (2 4), (2 5), (2 6), (2 7), (2 8)$.

Există $8$ oraşe. Se vor construi $3$ noi străzi. După construcţia străzii $2 4$, se vor modifica distanţele dintre următoarele perechi de oraşe: $(1 4)$, $(1 5)$, $(1 6)$, $(1 7)$, $(1 8)$, $(2 4)$, $(2 5)$, $(2 6)$, $(2 7)$, $(2 8)$.

== include(page="template/taskfooter" task_id="minuni") ==

4778