Гра з многокутником

Limits: 2 sec., 256 MiB

Зеник і Марічка досвідчені ковзанярі. Їм не хочеться просто кататися, тому вони придумали таку гру.

Перед початком гри Зеник віртуозно рисує ковзанами на льоду опуклий \(n\)-кутник.

Коли многокутник готовий, гравці починають ходити по черзі. Марічка ходить першою.

За один хід гравець може вибрати діагональ многокутника та проїхати вздовж неї, прорізаючи лід. Діагональ розділить многокутник на два менші многокутники. Тоді гравець вибирає одну з двох частин, на якій буде продовжуватися гра. На цьому хід закінчується.

Гра завершується, коли залишився трикутник.

Марічка хоче максимізувати площу трикутника, що залишиться, Зеник — мінімізувати.

Яка буде площа при оптимальній грі обох гравців?

Input

У першому рядку записано ціле число \(n\) — кількість вершин многокутника.

У наступних \(n\) рядках задано по два цілих числа \(x_i\), \(y_i\) — координати вершин многокутника в порядку обходу проти годинникової стрілки.

Output

Виведіть ціле число — подвоєну площу трикутника, що залишиться після завершення гри.

Можна довести, що подвоєна площа трикутника з вершинами в цілочисельних точках є цілою.

Constraints

\(4 \le n \le 10^5\),

\(|x_i|, |y_i| \le 10^9\),

жодні три вершини многокутника не лежать на одній прямій.

7 балів: \(n \le 15\);

8 балів: \(n \le 10^3\);

10 балів: без додаткових обмежень.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 0 0 7 4 3 11 -4 7	65

Input (stdin) сopy	Output (stdout) сopy
20 -20 5 -20 1 -19 -3 -17 -7 -15 -9 -13 -10 -11 -10 5 -8 12 -7 15 -6 17 -4 18 -1 18 3 17 6 15 8 12 9 8 9 -5 8 -14 7 -19 6	4

Notes

У першому прикладі після першого ходу Марічки гра завершиться. Незалежно від того, яку діагональ вона вибере, квадрат поділиться на два рівні трикутники.

У другому прикладі один з можливих сценаріїв такий. Марічка прорізає діагональ між вершинами \((-15, -9)\) і \((5, -8)\) (фіолетову) та залишає для гри верхню частину. Зеник проводить діагональ між вершинами \((-20, 5)\) і \((-19, -3)\) (зелену) та залишає трикутник. На цьому гра закінчується.