Maximum number of intersections on the chart

impl Solution {
  pub fn max_intersection_count(y: Vec<i32>) -> i32 {
    let n = y.len();
    // For each segment from (k, y[k]) to (k+1, y[k+1]), a horizontal line at height h
    // intersects this segment if h is strictly between y[k] and y[k+1].
    // A horizontal line also intersects at a point if it passes through a point.
    // 
    // Use coordinate compression + sweep line with events.
    // For each segment (y[i], y[i+1]):
    //   - The segment covers the open interval (min, max) of y[i], y[i+1]
    //   - At endpoints, we need to be careful about double counting
    // 
    // We use the trick of mapping each y value to 2*y, and treating endpoints
    // as point events at 2*y[i], while segment interiors span (2*min+1, 2*max-1).
    // 
    // Actually, a cleaner approach:
    // For each segment i (from point i to point i+1), a horizontal line at y=h
    // intersects the segment if h is strictly between y[i] and y[i+1].
    // At point i (not an endpoint of the chart), the line passes through the point
    // if y[i] == h, which counts as intersection with both adjacent segments.
    // But actually for intersection counting with a line chart, we count how many
    // times the line crosses or touches the chart segments.
    //
    // Better approach using sweep line on doubled coordinates:
    // Map each y-value to 2*y. Each segment from y[i] to y[i+1] covers
    // [2*min(y[i],y[i+1]), 2*max(y[i],y[i+1])].
    // But endpoints at vertices (not chart endpoints) would be double counted.
    // For interior vertices, we need to avoid double counting.
    //
    // Standard approach: use events with doubled coordinates.
    // Segment from y[i] to y[i+1]:
    //   lo = 2*min(y[i], y[i+1]) + 1
    //   hi = 2*max(y[i], y[i+1]) - 1
    // This covers the open interior.
    // For y[i] at index i (0 < i < n-1), if both adjacent segments contain y[i],
    // it adds 1 intersection at y=2*y[i]. But it's a vertex - we handle separately.
    //
    // Actually let me use a simpler known approach:
    // For each segment from point i to i+1:
    //   The segment crosses horizontal line at any height strictly between y[i] and y[i+1].
    //   At the endpoints, we need careful handling.
    //
    // Use doubled coordinates. For segment from y[i] to y[i+1]:
    //   let lo = min(y[i], y[i+1]), hi = max(y[i], y[i+1])
    //   Add event: +1 at 2*lo (if i>0 then 2*lo+1 else 2*lo) 
    //   Add event: -1 at 2*hi (if i<n-2 then 2*hi-1 else 2*hi) + 1
    //
    // Hmm, let me think more carefully. 
    // 
    // Each line segment i (from point i to point i+1) is intersected by y=h
    // if min(y[i],y[i+1]) <= h <= max(y[i],y[i+1]).
    // But if h equals a non-endpoint vertex y[i] (0<i<n-1), it's shared by
    // segments i-1 and i, but should only count once (tangent).
    // Actually no - a horizontal line passing through a vertex where the chart
    // changes direction may count as 1 intersection (if local extremum) or 
    // 2 intersections (if passes through).
    //
    // If y[i] is a local extremum, the line at y=y[i] touches but doesn't cross,
    // counting as 1 intersection (with both segments combined).
    // If y[i] is not a local extremum (monotone through), the line crosses both
    // segments, counting as 2 intersections.
    //
    // But since no two consecutive points have the same y-value, every vertex
    // is either a local max or local min.
    // So at each vertex (non-endpoint), the line at y=y[i] counts as 1 intersection.
    //
    // Use doubled coordinates:
    // For segment i (point i to i+1):
    //   lo = min(y[i], y[i+1]), hi = max(y[i], y[i+1])
    //   Open interval: 2*lo+1 to 2*hi-1 always contributes
    //   At endpoint y[i]: contributes if i==0 (left end of chart) - always contributes
    //   At endpoint y[i+1]: contributes if i+1==n-1 (right end of chart) - always contributes
    //
    // For the first segment: covers [2*lo, 2*hi] on doubled scale
    //   but the top point shared with next segment if not last
    //   The bottom endpoint: if y[0]<y[1], bottom is at y[0] which is chart start
    //     -> include 2*y[0]
    //   The top endpoint: if y[1]>y[0], top is at y[1]
    //     -> if 1 is interior vertex and local max, don't include 2*y[1] 
    //        (will be counted by vertex handling)
    //
    // Let me use a cleaner standard approach:
    // For segment i:
    //   lo = min(y[i], y[i+1]), hi = max(y[i], y[i+1])
    //   start = 2*lo, end = 2*hi
    //   If i > 0: start += 1  (the lower endpoint is a vertex, handled separately)
    //   If i < n-2: end -= 1  (the upper endpoint is a vertex, handled separately)
    //   Add sweep event +1 at start, -1 at end+1
    //
    // Wait, I need to be more careful. The "lower" endpoint of the segment 
    // may be on either side (point i or i+1). Let's think about which endpoint
    // corresponds to which vertex.
    //
    // For segment i:
    //   It connects vertex i and vertex i+1
    //   Vertex i is a chart endpoint if i==0, interior otherwise
    //   Vertex i+1 is a chart endpoint if i+1==n-1, interior otherwise
    //   At an interior vertex, the line touches but doesn't fully cross (local extremum)
    //   So at 2*y[vertex] for interior vertex, we should count only 1 from the two
    //   adjacent segments.
    //
    // So for each segment i from vertex i to vertex i+1:
    //   lo = min(y[i], y[i+1]), hi = max(y[i], y[i+1])
    //   range on doubled scale:
    //     lower_bound = if the vertex at lo is interior then 2*lo+1 else 2*lo
    //     upper_bound = if the vertex at hi is interior then 2*hi-1 else 2*hi
    //
    // The vertex at lo: if y[i] < y[i+1], lo-vertex is i, else i+1
    // The vertex at hi: if y[i] > y[i+1], hi-vertex is i, else i+1
    //
    // Vertex i is interior if 0 < i, vertex i+1 is interior if i+1 < n-1
    //
    // Then for each interior vertex v, add a point event at 2*y[v]: +1
    //
    // Sweep to find max.
    
    use std::collections::BTreeMap;
    let mut events: BTreeMap<i64, i32> = BTreeMap::new();
    
    for i in 0..n-1 {
      let a = y[i] as i64;
      let b = y[i+1] as i64;
      let lo = a.min(b);
      let hi = a.max(b);
      
      // Determine which vertex is at lo and hi
      let lo_vertex = if a < b { i } else { i + 1 };
      let hi_vertex = if a > b { i } else { i + 1 };
      
      let lower = if lo_vertex > 0 && lo_vertex < n - 1 {
        2 * lo + 1
      } else {
        2 * lo
      };
      let upper = if hi_vertex > 0 && hi_vertex < n - 1 {
        2 * hi - 1
      } else {
        2 * hi
      };
      
      if lower <= upper {
        *events.entry(lower).or_insert(0) += 1;
        *events.entry(upper + 1).or_insert(0) -= 1;
      }
    }
    
    // Add point events for interior vertices
    for i in 1..n-1 {
      let val = 2 * y[i] as i64;
      *events.entry(val).or_insert(0) += 1;
      *events.entry(val + 1).or_insert(0) -= 1;
    }
    
    let mut ans = 0;
    let mut cur = 0;
    for (_, v) in &events {
      cur += v;
      ans = ans.max(cur);
    }
    ans
  }
}