<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

300. Train
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



The restoration of the old Berland railroad has been finished at last. From above the railroad has the form of the polyline possibly with self-intersections but without self-covering. All segments of the polyline are either parallel or perpendicular to the earth equator line, which is considered to be a straight line.

Ministers now have a very difficult task. They have to determine the length of the train traveling back and forth. The decision was made to minimize the fuel expenses. To achieve this goal the length of the train should be maximal. There and then the assumption was made that the length of the train should be equal to the length of the railroad. In this case the fuel expenses will be equal to zero. The problem is that the train cannot have any self-intersections and self-touchings at any moment of time, although the head and the tail can occupy the same point. That's why the length of the train should possibly be reduced. Your task is to find the maximum possible length of the train. You can neglect the width of the rails and consider it equals to zero.

Input
The first line of the input contains integer number N (1≤ N≤ 4000) — the number of vertices in the polyline. The following lines contain the coordinates of the vertices — the pairs of integers xi, yi. Coordinates values are not greater than 10000 by absolute value. The train will pass the vertices in order they are listed in the input. All segments of polyline are parallel to the grid axis.

Output
Write to the output the unknown maximum length of the train.

Example(s)
sample input
sample output
5
0 0
3 0
3 1
1 1
1 -1
6

sample input
sample output
7
0 0
1 0
1 1
3 1
3 0
1 0
1 -1
6

<|response|>
## 1) Abridged problem statement (concise)

You are given an axis-aligned polyline (railroad) with \(N\) vertices \((x_i,y_i)\), \(1 \le N \le 4000\). A train moves along the polyline in the given order. At any time, the train occupies a **continuous** part of the polyline of length \(L\) (tail behind head along the path).

Constraint: during motion, the train’s shape in the plane must **never self-intersect or self-touch** (except the head and tail may coincide at one point).

Compute the **maximum possible** train length \(L\).

---

## 2) Key observations

1. **Train at time \(t\) = subcurve of the polyline.**  
   Since the train occupies a continuous interval of arc-length along the path, at any moment it is exactly some subpath \([s, s+L]\).

2. **Self-touch happens when the subpath contains the same plane point twice.**  
   The polyline has no overlapping segments (“no self-covering”), so the only way two different arc-length positions map to the same point is:
   - a proper intersection between a **horizontal** and **vertical** segment, or
   - revisiting a vertex (which is also an intersection at an endpoint).

3. **Every intersection defines a “loop length” that upper-bounds \(L\).**  
   Suppose the polyline reaches a point \(P\) at arc-length positions \(d_1 < d_2\).  
   Then the subpath from \(d_1\) to \(d_2\) is a closed walk in the plane of length:
   \[
   \text{loopLen} = d_2 - d_1
   \]
   If \(L > \text{loopLen}\), then at some moment the train interval \([s,s+L]\) will contain both occurrences of \(P\), forcing a self-touch.  
   Therefore:
   \[
   L \le \min(\text{loopLen over all repeated points})
   \]

4. **So the answer is the minimum loop length over all non-adjacent segment intersections, or total length if none.**

---

## 3) Full solution approach

### Step A: Precompute arc-length positions (prefix sums)
Let there be \(m = N-1\) segments (segment \(i\) connects vertex \(i\) to \(i+1\)).  
All segments are axis-aligned, so segment length is Manhattan distance.

Compute:
- `pref[0] = 0`
- `pref[i+1] = pref[i] + length(segment i)` for \(i=0..m-1\)

Then `pref[k]` = distance along the track from the start to vertex \(k\).  
Total track length = `pref[m]`.

### Step B: Check all relevant segment pairs for intersections
Because \(N \le 4000\), an \(O(N^2)\) scan of segment pairs is acceptable in typical settings (and matches the reference solution).

For each pair of segments \((i,j)\) with \(j \ge i+2\):
- We skip adjacent segments because they meet at a common endpoint and that is not a “self” intersection.
- Determine if they intersect:
  - Only possible (without overlap) if one is horizontal and the other vertical.
  - Standard range check gives intersection point \((px,py)\) (including endpoint touching).

### Step C: Convert an intersection point into a loop length
If segments \(i\) and \(j\) intersect at point \(P=(px,py)\), compute the arc-length position where the polyline reaches \(P\) on each segment:

\[
d(i,P) = \text{pref}[i] + |px - x_i| + |py - y_i|
\]

Similarly for \(j\). If \(i < j\), then \(d_i < d_j\) and:
\[
\text{loopLen} = d_j - d_i
\]

Update:
- `ans = min(ans, loopLen)`

### Step D: Output
Initialize `ans = total_length`.  
After scanning all pairs, print `ans`.

If there are no intersections, `ans` remains total length, meaning the whole track can be occupied without self-touching.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<pair<int,int>> p(N);
    for (int i = 0; i < N; i++) cin >> p[i].first >> p[i].second;

    // If there is only one vertex, there are no segments => length 0.
    if (N <= 1) {
        cout << 0 << "\n";
        return 0;
    }

    int m = N - 1; // number of segments

    auto seg_len = [&](int i) -> ll {
        // Segments are axis-aligned, so Manhattan distance equals segment length.
        return ll(abs(p[i+1].first - p[i].first)) + ll(abs(p[i+1].second - p[i].second));
    };

    // Prefix lengths: pref[k] = distance from start to vertex k.
    vector<ll> pref(m + 1, 0);
    for (int i = 0; i < m; i++) pref[i + 1] = pref[i] + seg_len(i);

    // Distance along the track to reach point (px,py) while traveling on segment i.
    auto pos_on_track = [&](int i, int px, int py) -> ll {
        return pref[i] + ll(abs(px - p[i].first)) + ll(abs(py - p[i].second));
    };

    // Compute intersection point of segments i and j if they intersect; otherwise return false.
    // Only meaningful for "one horizontal, one vertical" (since overlapping is disallowed).
    auto get_intersection = [&](int i, int j, int &px, int &py) -> bool {
        bool hi = (p[i].second == p[i+1].second); // segment i horizontal?
        bool hj = (p[j].second == p[j+1].second); // segment j horizontal?

        // Same orientation => no proper crossing (overlaps are forbidden by statement).
        if (hi == hj) return false;

        // Ensure i is horizontal, j is vertical (swap indices if needed).
        if (!hi) swap(i, j);

        // Now: segment i is horizontal, segment j is vertical.
        int hx1 = min(p[i].first, p[i+1].first);
        int hx2 = max(p[i].first, p[i+1].first);
        int hy  = p[i].second;

        int vx  = p[j].first;
        int vy1 = min(p[j].second, p[j+1].second);
        int vy2 = max(p[j].second, p[j+1].second);

        // They intersect iff vx is within [hx1,hx2] and hy is within [vy1,vy2].
        if (hx1 <= vx && vx <= hx2 && vy1 <= hy && hy <= vy2) {
            px = vx;
            py = hy;
            return true;
        }
        return false;
    };

    ll ans = pref[m]; // total length is feasible if there are no self-intersections.

    // Check all non-adjacent segment pairs.
    // j >= i+2 skips adjacent segments sharing a vertex.
    for (int i = 0; i < m; i++) {
        for (int j = i + 2; j < m; j++) {
            int px, py;
            if (!get_intersection(i, j, px, py)) continue;

            // Arc-length positions of the same geometric point.
            ll di = pos_on_track(i, px, py);
            ll dj = pos_on_track(j, px, py);

            // Since j > i in this loop, dj should be >= di.
            // The loop length is the distance along the polyline between two visits.
            ans = min(ans, dj - di);
        }
    }

    cout << ans << "\n";
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
from typing import List, Tuple, Optional

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)

    N = int(next(it))
    p: List[Tuple[int, int]] = [(int(next(it)), int(next(it))) for _ in range(N)]

    # No segments => length 0
    if N <= 1:
        print(0)
        return

    m = N - 1  # number of segments

    def seg_len(i: int) -> int:
        """Length of segment i (axis-aligned => Manhattan distance)."""
        x1, y1 = p[i]
        x2, y2 = p[i + 1]
        return abs(x2 - x1) + abs(y2 - y1)

    # Prefix sums of lengths: pref[k] = distance from start to vertex k
    pref = [0] * (m + 1)
    for i in range(m):
        pref[i + 1] = pref[i] + seg_len(i)

    def pos_on_track(i: int, px: int, py: int) -> int:
        """Arc-length position to point (px,py) along segment i."""
        x, y = p[i]
        return pref[i] + abs(px - x) + abs(py - y)

    def get_intersection(i: int, j: int) -> Optional[Tuple[int, int]]:
        """
        Return intersection point of segments i and j, or None if they don't intersect.
        Only considers one horizontal + one vertical segment.
        """
        x1, y1 = p[i]
        x2, y2 = p[i + 1]
        x3, y3 = p[j]
        x4, y4 = p[j + 1]

        hi = (y1 == y2)  # segment i horizontal?
        hj = (y3 == y4)  # segment j horizontal?

        if hi == hj:
            # Same orientation: no proper crossing; overlap is forbidden.
            return None

        # Ensure i is horizontal and j is vertical by swapping if needed
        if not hi:
            i, j = j, i
            x1, y1 = p[i]
            x2, y2 = p[i + 1]
            x3, y3 = p[j]
            x4, y4 = p[j + 1]

        # Horizontal i: y fixed, x in [hx1,hx2]
        hx1, hx2 = (x1, x2) if x1 <= x2 else (x2, x1)
        hy = y1

        # Vertical j: x fixed, y in [vy1,vy2]
        vx = x3
        vy1, vy2 = (y3, y4) if y3 <= y4 else (y4, y3)

        if hx1 <= vx <= hx2 and vy1 <= hy <= vy2:
            return (vx, hy)
        return None

    ans = pref[m]  # total length if no intersections exist

    # Check all non-adjacent segment pairs
    for i in range(m):
        for j in range(i + 2, m):
            inter = get_intersection(i, j)
            if inter is None:
                continue
            px, py = inter
            di = pos_on_track(i, px, py)
            dj = pos_on_track(j, px, py)
            ans = min(ans, dj - di)

    print(ans)

if __name__ == "__main__":
    solve()
```

