Lost in Darkness

Farmer John’s barn is a simple, axis‐aligned polygon with vertices given in clockwise order. The exit is located at vertex 1. When the lights are on, Bessie (whose starting vertex is one of the other vertices) can quickly choose the shorter path (clockwise or counterclockwise) along the perimeter to reach the exit. However, when the lights go out Bessie forgets her starting position – though she remembers the barn's map perfectly.

In the dark, whenever Bessie reaches a vertex she can feel its interior angle (which, since the barn alternates between horizontal and vertical edges, is either \(90^\circ\) or \(270^\circ\)). Also, while traversing an edge she can determine its exact length. Bessie adopts the following strategy: she starts moving clockwise until the sequence of angles and edge‐lengths she has felt uniquely identifies her starting vertex. At that point, she computes the minimum additional distance needed to reach the exit (by either continuing clockwise or switching directions).

Your task is to compute the worst‐case extra distance Bessie might have to travel in the dark compared to the optimal (lit) travel, where the extra distance is defined as

[ \Delta = d_{dark} - d_{lit}, ]

and the answer is the maximum \(\Delta\) over all possible starting vertices (other than the exit).

Input Format: The barn is described by an integer \(n\) (the number of vertices) followed by \(n\) lines with integer coordinates for each vertex. The vertices are given in clockwise order. The exit is at vertex 1; Bessie starts at one of the vertices 2 through \(n\). Edges alternate between horizontal and vertical.

Output Format: Output a single integer, which is the largest amount by which Bessie’s travel distance in the dark will exceed the optimal lit distance.

Note on angles: Since the barn’s edges alternate between horizontal and vertical, the interior angle at any vertex is either \(90^\circ\) (when turning right) or \(270^\circ\) (when turning left). For a clockwise polygon, if the cross product computed at a vertex is negative then the interior angle is \(90^\circ\); if it is positive then the interior angle is \(270^\circ\).

inputFormat

The first line contains a single integer \(n\) (number of vertices, \(4 \le n \le 200\)). Each of the next \(n\) lines contains two space‐separated integers \(x_i\) and \(y_i\) (\(|x_i|, |y_i| \le 10^4\)). The vertices are given in clockwise order, and edges alternate between horizontal and vertical. Vertex 1 (first vertex) is the exit.

outputFormat

Output a single integer representing the largest extra distance Bessie could have to travel in the dark compared to when the barn is lit.

sample

4
0 0
0 1
1 1
1 0

2