Problema: Primar / 
Autor: Primarul orașului tocmai a aprobat un proiect pentru construirea unui ștrand la periferia localității. Zona pe care se dorește a fi amplasat ștrandul se poate identifica cu planul 2D (infinit). Aceasta conține N arbori, aflați la coordonate întregi, cu lățimea de 1 metru. Nu există doi arbori la aceeași coordonată x sau y. Mai exact, xi ≠ xj și yi ≠ yj, pentru orice i ≠ j.
Ștrandul nu poate fi amplasat decât în locații de forma unui dreptunghi cu laturile paralele cu axele, care, din motive de sustenabilitate, nu trebuie să conțină în interiorul său niciunul dintre arbori. Mai mult, deoarece bugetul pentru acest proiect este foarte generos, primarul este interesat doar de acele zone maximale (care nu pot fi extinse). Cu alte cuvinte, o regiune S nu este validă dacă există o altă regiune S' ≠ S dreptunghiulară, cu laturile paralele cu axele, care nu conține niciun arbore, iar S ⊂ S'.
De exemplu, pentru cazul ilustrat în figura alăturată (primul din secțiunea de exemple) se disting două posibilități valide de amplasare a ștrandului: cea roșie (de arie 2 x 6 = 12) și cea albastră (de arie 4 x 5 = 20).
Cerința
Care este suma ariilor tuturor regiunilor valide posibile? Rezultatul se va afișa modulo 1.000.000.007.
Date de intrare
Fișierul de intrare primar.in conține pe prima linie N, numărul de arbori. Pe următoarele N linii se vor găsi câte două valori întregi xi, yi (1 ≤ i ≤ N) separate printr-un spațiu, reprezentând coordonatele arborilor. Arborele i este reprezentat printr-un pătrat de latură 1 centrat în punctul de coordonate (xi , yi).
Date de ieșire
Fișierul de ieșire primar.out va conține un singur număr natural, reprezentând suma ariilor tuturor regiunilor valide, modulo 1.000.000.007.
Restricții și precizări
1 ≤ N ≤ 5000,1 ≤ xi, yi≤ 1.000.000- Pentru toate testele,
xi≠ xjșiyi≠ yj, pentru oricei ≠ j.
Exemplul 1:
primar.in
5 1 4 4 3 2 2 6 6 3 9
primar.out
32
Exemplul 2:
primar.in
2 1 1 2 3
primar.out
0
Exemplul 3:
primar.in
7 1 1 2 5 4 2 3 7 8 3 9 6 10 4 52 2
primar.out
52
