Gary a essayé de générer des polygones orthogonaux simples pour ses devoirs de géométrie, mais son algorithme semble poser quelques problèmes. Après quelques bonnes heures de débogage, il a finalement réalisé quel était le problème : apparemment, les polygones qu'il générait pouvaient contenir des auto-intersections, ce qui n'était pas du tout ce qu'il voulait !

Plus précisément, les « polygones » que Gary a générés sont représentés par une liste de $n$ points $p_i = (x_i, y_i)$, formant une chaîne polygonale fermée. La chaîne polygonale peut contenir des auto-intersections. Les segments formés par deux points consécutifs $(x_i, y_i)$ et $(x_j, y_j)$ dans la chaîne sont soit verticaux, soit horizontaux.

Les chaînes polygonales pour les exemples de tests sont illustrées ci-dessous (pas à l'échelle) :

Vous avez décidé d'aider Gary à résoudre ce problème en calculant un polygone simple (sans auto-intersection) avec des segments verticaux et horizontaux qui contient entièrement la chaîne, et dont l'aire est aussi petite que possible. Quelle est l'aire d'un tel polygone ?

Formellement, vous devez calculer l'infimum des aires de tous les polygones orthogonaux simples qui contiennent tous les segments $[p_i, p_j]$, pour chaque paire de points adjacents $p_i$ et $p_j$.

Entrée

La première ligne de l'entrée contiendra un entier positif $n$ ($4 \le n \le 100\,000$). Les $n$ lignes suivantes contiendront les points $(x_i, y_i)$ dans l'ordre ($1 \le x_i, y_i \le 10^6$). Aucun point consécutif ne coïncide, et il n'y a pas deux segments verticaux consécutifs ou deux segments horizontaux consécutifs.

Sortie

Affichez un seul entier non négatif, l'infimum des aires de tous les polygones simples qui enferment la chaîne polygonale fermée. Il peut être prouvé que la réponse est toujours un entier.

Exemples

Entrée 1

6
1 1
6 1
6 11
11 11
11 6
1 6

Sortie 1

50

Entrée 2

8
2 4
2 1
4 1
4 3
1 3
1 2
3 2
3 4

Sortie 2

6

Entrée 3

10
1 1
1 5
4 5
4 3
2 3
2 4
1 4
1 2
4 2
4 1

Sortie 3

8

Remarque

Dans les exemples 1 et 3, il n'existe pas de polygones simples ayant des aires exactement égales à 50 et 8, respectivement ; cependant, il existe des polygones simples dont les aires sont arbitrairement proches de ces valeurs.