## 1) Abridged problem statement

You are given a polyline “mountain” with vertices \((1,y_1),(2,y_2),\dots,(n,y_n)\). Two climbers start at the ends: one at \((1,y_1)\) and the other at \((n,y_n)\). They move along the polyline edges (possibly stopping or moving at any speeds), but **at every moment they must be at the same height (same \(y\))**.
Given that \(y_1=y_n=0\), determine whether it is possible for them to **meet at the same point** on the mountain while respecting the equal-height constraint. Output `"YES"` or `"NO"`.

---

## 2) Detailed editorial (how the solution works)

### Key idea: what does “same height at all times” imply?
At any moment both climbers have the same vertical coordinate \(y\). So the process can be viewed as choosing a height \(y(t)\) over time, and having each climber stand somewhere on their respective side of the mountain where the polyline has that height.

This is the classic “mountain climbing” problem, where for non-negative heights the answer is always `YES` (a parity argument on the graph of position pairs shows the start \((1,n)\) and the swapped state \((n,1)\) lie in the same connected component, hence some \((x,x)\) meeting state is reachable). However, here heights may be negative, which can introduce extra degree-1 vertices and break that parity argument, so meeting can genuinely be impossible. We therefore simulate the climbing explicitly.

### Maintain an invariant: a *feasible height interval*
The solution uses a greedy two-pointer approach.

- Let `l` be the current vertex index of the **left** climber (starting `l=0`).
- Let `r` be the current vertex index of the **right** climber (starting `r=n-1`).
- Maintain an interval `[low, high]` of heights such that:

> From the current positions (somewhere between vertices near `l` and `r`), the climbers can “synchronize” at **any** common height in `[low, high]` without leaving their already-reachable regions. The key fact that makes this work is that by backtracking they can reach any already-visited point at any height in `[low, high]`.

Initially:
- both are at height 0, so `low = high = 0`.

At each step we try to move inward (increase `l` or decrease `r`) while keeping feasibility.

### What does it mean to “move one step inward”?
Consider trying to advance the left climber from vertex `l` to `l+1`. The height at the next vertex is `h[l+1]`.

There are four cases (the code checks them in this order):

#### Case 1: Safe advance (no interval change)
If `h[l+1]` lies inside the current feasible interval `[low, high]`, then the left climber can advance to `l+1` while the right climber can adjust (possibly by moving/stopping) to maintain equal height within the same interval.
So we do `l++`.
Symmetrically, if `h[r-1]` is inside `[low, high]`, we can do `r--`.

#### Case 2: Both next vertices are above `high` (must climb higher)
If `h[l+1] > high` and `h[r-1] > high`, then to keep equal height, they must raise their synchronized height above `high`. The best we can do is raise `high` to the **smaller** of those two next heights, and move that corresponding pointer inward, because that side reaches the new required ceiling first.
- If `h[l+1] < h[r-1]`, set `high = h[l+1]`, `l++`
- else set `high = h[r-1]`, `r--`

This preserves feasibility: now `[low, high]` expands upward just enough to allow progress.

#### Case 3: Both next vertices are below `low` (must descend lower)
Similarly, if `h[l+1] < low` and `h[r-1] < low`, they must lower their synchronized height below `low`. We decrease `low` to the **larger** of the two (closest to current interval), and move that pointer.
- If `h[l+1] > h[r-1]`, set `low = h[l+1]`, `l++`
- else set `low = h[r-1]`, `r--`

#### Case 4: Mixed situation ⇒ impossible
If one side would need to go above `high` while the other would need to go below `low` (or one fits but neither of the “safe advance” checks passed), then there is no single height that both can share while moving inward. Then output `"NO"`.

### Termination
We repeat until `l >= r`. At that point, their reachable regions overlap (they have effectively met or crossed), and the algorithm concludes `"YES"`.

### Complexity
Each step increments `l` or decrements `r`, so there are at most `n-1` steps:
- Time: **O(n)**
- Memory: **O(1)** beyond the input array.

This fits the strict time limit.

---

## 3) C++ Solution

```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<int> h;

void read() {
    cin >> n;
    h.resize(n);
    cin >> h;
}

void solve() {
    // We could try to think of constructions, or quadratic DP solutions, but
    // actually it's always possible! This is known as the mountain climbing
    // problem, and it's true for any continuous function with a finite number
    // of "peaks". The wiki page below has a good proof, which roughly goes as
    // follows: Consider the graph with nodes represented by the two coordinates
    // of the climbers (x1, x2). We start from (1, n), and want to get to some
    // (x, x). We will show something stronger - (n, 1) is reachable from (1,
    // n), meaning that the climbers will switch their place and this implies
    // there is some (x, x) where they meet. Also note that we can keep
    // everything discretely, as it's enough to only keep a finite number of
    // vertices where either x1 or x2 is a peak (local minimum/maximum). Now
    // let's look at the degree of every vertex. Trivially, (1, n) and (n, 1)
    // have degree one as we can't exit the mountain. The core observation is
    // that all other vertices will have an even degree (we can go through the
    // cases), meaning that the only two vertices with odd degree are (1, n) and
    // (n, 1). However, a connected component has to have an even number of odd
    // degree vertices, meaning that (1, n) and (n, 1) are in the same connected
    // component. Therefore, we have showed that for any landscape the answer is
    // YES. The alternative approaches that simulate the climbing can actually
    // lead to quadratic complexity while finding the construction, so here we
    // will simply print YES.
    //
    // Unfortunately, after trying this you get WA2. This is because heights
    // can be negative, which means the mountain can dip below the starting
    // level. In the classical mountain climbing problem all heights are
    // non-negative, so (1, n) and (n, 1) are the only degree-1 vertices. With
    // negative heights, additional degree-1 vertices can appear, breaking the
    // parity argument. The correct approach is to actually try moving the two
    // climbers. Let's keep l and r, denoting the rightmost position of the lest
    // one, and the leftmost position of the right one. We will also maintain
    // the set of heights they can occupy denoted by low and high. Trivially, we
    // start from (l=1, r=n, low=0, high=0). The key observation is that when we
    // backtrack, we can reach i < l, or j > r, at any of the heights between
    // low and high. This means we only have the following cases:
    //
    //     1) Safe advance (no range change needed). If the next left vertex
    //       h[l+1] is inside [low, high], the left alpinist can move forward
    //       (right can pause/adjust to match height). There is an equivalent
    //       case for right alpinist moving.
    //
    //     2) Both must climb higher h[l+1] > high and h[r-1] > high. Then we
    //        can just get them closer together, to the lower of the two heights
    //        and update high (we move only one of the alpinist).
    //
    //     3) Both must climb lower h[l+1] < low and h[r-1] < low. Then we
    //        can just get them closer together, to the higher of the two
    //        heights and update low (we move only one of the alpinist).
    //
    //     4) In any other case, the answer is NO.
    //
    // If we eventually get to l >= r, we can terminate.

    int l = 0, r = n - 1;
    int low = 0, high = 0;
    while(l < r) {
        if(h[l + 1] >= low && h[l + 1] <= high) {
            l++;
        } else if(h[r - 1] >= low && h[r - 1] <= high) {
            r--;
        } else if(h[l + 1] > high && h[r - 1] > high) {
            if(h[l + 1] < h[r - 1]) {
                high = h[l + 1];
                l++;
            } else {
                high = h[r - 1];
                r--;
            }
        } else if(h[l + 1] < low && h[r - 1] < low) {
            if(h[l + 1] > h[r - 1]) {
                low = h[l + 1];
                l++;
            } else {
                low = h[r - 1];
                r--;
            }
        } else {
            cout << "NO" << endl;
            return;
        }
    }

    cout << "YES" << 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;
}
```

---

## 4) Python solution (same logic, detailed comments)

```python
import sys

def solve() -> None:
    data = list(map(int, sys.stdin.read().strip().split()))
    n = data[0]
    h = data[1:1+n]

    # Two pointers at the ends (0-based indices)
    l, r = 0, n - 1

    # Feasible synchronized height interval [low, high]
    # Start at height 0 on both ends (given by statement)
    low = high = 0

    while l < r:
        # Case 1: safe advance from left if next height is within [low, high]
        if low <= h[l + 1] <= high:
            l += 1

        # Case 1 (symmetric): safe advance from right
        elif low <= h[r - 1] <= high:
            r -= 1

        # Case 2: both next heights above current high -> must raise high
        elif h[l + 1] > high and h[r - 1] > high:
            # Raise to the smaller one and move that pointer inward
            if h[l + 1] < h[r - 1]:
                high = h[l + 1]
                l += 1
            else:
                high = h[r - 1]
                r -= 1

        # Case 3: both next heights below current low -> must lower low
        elif h[l + 1] < low and h[r - 1] < low:
            # Lower to the larger one and move that pointer inward
            if h[l + 1] > h[r - 1]:
                low = h[l + 1]
                l += 1
            else:
                low = h[r - 1]
                r -= 1

        # Case 4: incompatible; cannot choose a single synchronized height
        else:
            sys.stdout.write("NO\n")
            return

    sys.stdout.write("YES\n")

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

---

## 5) Compressed editorial

Maintain pointers `l=0`, `r=n-1` and a feasible synchronized height interval `[low, high]` (start `[0,0]`).
While `l<r`:

- If `h[l+1]∈[low,high]`, do `l++`; else if `h[r-1]∈[low,high]`, do `r--`.
- Else if both `h[l+1], h[r-1] > high`, raise `high` to `min(h[l+1], h[r-1])` and move the side achieving it.
- Else if both `h[l+1], h[r-1] < low`, lower `low` to `max(h[l+1], h[r-1])` and move that side.
- Otherwise, impossible ⇒ `"NO"`.

If the loop ends, they can meet ⇒ `"YES"`.
Runs in O(n).
