<|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;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<pair<int, int>> p;
vector<int64_t> prefix_len;

int64_t seg_len(int i) {
    return abs(p[i + 1].first - p[i].first) +
           abs(p[i + 1].second - p[i].second);
}

optional<pair<int, int>> get_intersection(int i, int j) {
    bool h1 = (p[i].second == p[i + 1].second);
    bool h2 = (p[j].second == p[j + 1].second);

    if(h1 == h2) {
        return nullopt;
    }

    if(!h1) {
        swap(i, j);
    }

    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);

    if(vx >= hx1 && vx <= hx2 && hy >= vy1 && hy <= vy2) {
        return make_pair(vx, hy);
    }

    return nullopt;
}

int64_t pos_on_track(int i, int px, int py) {
    return prefix_len[i] + abs(px - p[i].first) + abs(py - p[i].second);
}

void read() {
    cin >> n;
    p.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
    }
}

void solve() {
    // The train occupies a contiguous portion of the track. As it moves,
    // different parts of the track are covered, meaning that the train
    // self-intersects when two different positions along the track map to the
    // same point P (or there is a cycle). We will anyways pass through every
    // cycle, meaning that we are bounded by the "shortest one". This means we
    // can simply try all possible pairs of segments, and if they intersect we
    // can directly figure out the length of the cycle: it's the length(start,
    // B) - length(start, A). Note that this might not be a simple cycle, but if
    // that's the case there is certainly a smaller one which we would consider
    // in this algorithm too. The complexity of this algorithm is O(N^2) which
    // is sufficient for the problem here.

    if(n <= 1) {
        cout << 0 << endl;
        return;
    }

    int m = n - 1;
    prefix_len.resize(m + 1);
    prefix_len[0] = 0;
    for(int i = 0; i < m; i++) {
        prefix_len[i + 1] = prefix_len[i] + seg_len(i);
    }

    int64_t ans = prefix_len[m];

    for(int i = 0; i < m; i++) {
        for(int j = i + 2; j < m; j++) {
            auto intersection = get_intersection(i, j);
            if(intersection) {
                auto [px, py] = *intersection;
                int64_t pos_i = pos_on_track(i, px, py);
                int64_t pos_j = pos_on_track(j, px, py);
                ans = min(ans, pos_j - pos_i);
            }
        }
    }

    cout << ans << endl;
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    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()
```
