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

380. Synchronised Alpinism
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

The progress does not stand! An institute of Sport Experiments (SE) is preparing new surprises for future Olympic Games. There is no doubt that you are familiar with synchronised swimming. But do you know anything about synchronised boxing or synchronised basketball? In this problem we will consider only synchronised alpinism. It is a team competition, each team consists of two members. Initially one of them stands at the east side of the mountain and other — at the west side. Their aim is to meet at some point as fast as possible. There is also one additional difficulty: at any moment of time they have to be at the same height. Unfortunatly, SE's synchronised alpinism experimental contest was unsuccessful. No team managed to fulfill the task, so it was impossible to determine a winner! Now SE is interested, is it really impossible to meet on the mountain under above restrictions or the teams just have to train harder. Try to help SE!
Input
Here we will assume that mountain is flat figure, and its border is a polyline, with a peaks at points (1, y1),..., (n, yn). The first line of the input file consists one integer number n (). The second line contains integer numbers y1,..., yn. Points (1, y1) and (n, yn) are initial positions of alpinists. It is guaranteed that y1=0, yn=0 and y1,..., yn do not exceed  by absolute value.
Output
If it is possible for the alpinists to meet, output "YES", otherwise output "NO" (quotes for clarity).
Example(s)
sample input
sample output
7
0 3 1 5 2 4 0
YES

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

You are given a polyline (mountain border) with vertices \((1,y_1),(2,y_2),\dots,(n,y_n)\). Two climbers start at the ends: at \((1,y_1)\) and \((n,y_n)\), where \(y_1=y_n=0\). They can move along the polyline edges with any speed (including stopping), but **at every moment they must have the same height** (same \(y\)-coordinate).
Determine if it’s possible for them to **meet at the same point**. Output `"YES"` or `"NO"`.

---

## 2) Key observations

1. **Only the heights matter.** The x-coordinates are fixed (1..n). Movement is along edges between consecutive vertices, so each climber progresses inward along indices.

2. **Equal-height constraint ⇒ there must exist a common feasible height at all times.**
   At any moment, both climbers must stand at some points (possibly in the interior of edges) whose heights match. Because they may stop, the process is flexible—but the heights must remain synchronizable.

3. **Maintain a feasible height interval \([low, high]\).**
   While left pointer `l` and right pointer `r` indicate how far each climber has progressed, keep an invariant:

   > The climbers can be positioned (somewhere on their already-visited parts) at **any common height in \([low, high]\)**. By backtracking they can reach any already-visited point at any height in this interval.

   Initially both stand at height 0, so \([low,high]=[0,0]\).

4. **Greedy two-pointers works in O(n).**
   At each step, try to advance `l` or `r` by one vertex while preserving feasibility. If neither side can advance without breaking the common-height requirement, it’s impossible.

5. **Negative heights matter.**
   The classic “mountain climbing theorem” intuition (“always possible”) holds when all heights are non-negative, because then the position-pair graph has exactly two degree-1 vertices, \((1,n)\) and \((n,1)\), forcing them into the same connected component. With negative heights additional degree-1 vertices appear, the parity argument fails, and the algorithm must explicitly detect impossibility.

---

## 3) Full solution approach

Let `h[i] = y_{i+1}` be the heights in 0-based indexing (`i = 0..n-1`).

- Initialize:
  - `l = 0` (left climber at vertex 0)
  - `r = n-1` (right climber at vertex n-1)
  - `low = high = 0` (both start at height 0)

While `l < r`, consider next vertices `h[l+1]` and `h[r-1]`:

### Case A: “Safe advance” without changing \([low, high]\)
- If `h[l+1]` lies inside `[low, high]`, we can move left climber to `l+1` while right climber adjusts/stops to maintain a common height within the same interval. Do `l++`.
- Else if `h[r-1]` lies inside `[low, high]`, do `r--`.

### Case B: Both next heights are above `high` ⇒ must raise the common height
If `h[l+1] > high` **and** `h[r-1] > high`, then any common height must increase above `high`.
We raise `high` to the smaller of the two “required” heights and move that corresponding pointer inward:
- If `h[l+1] < h[r-1]`: set `high = h[l+1]`, `l++`
- Else: set `high = h[r-1]`, `r--`

This keeps the invariant: now feasible heights extend upward just enough to make progress.

### Case C: Both next heights are below `low` ⇒ must lower the common height
If `h[l+1] < low` **and** `h[r-1] < low`, similarly we must decrease.
Lower `low` to the larger (closer) of the two and move that side:
- If `h[l+1] > h[r-1]`: set `low = h[l+1]`, `l++`
- Else: set `low = h[r-1]`, `r--`

### Case D: Otherwise ⇒ impossible
Any mixed situation means the two sides “demand” incompatible height directions (one needs above `high` while the other needs below `low`, etc.), so there is no single height both can share at that step. Output `"NO"`.

### Termination
If the loop finishes (i.e., `l >= r`), their progress regions overlap/cross, meaning a synchronized meeting is achievable. Output `"YES"`.

**Complexity:** each step moves `l` or `r` once → at most `n-1` steps.
Time **O(n)**, extra space **O(1)**.

---

## 4) C++ implementation

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

---

## 5) Python implementation (detailed comments)

```python
import sys

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

    # Two pointers from ends
    l, r = 0, n - 1

    # Feasible synchronized height interval [low, high]
    low = high = 0

    while l < r:
        hl = h[l + 1]
        hr = h[r - 1]

        # Case A1: safe advance on the left
        if low <= hl <= high:
            l += 1

        # Case A2: safe advance on the right
        elif low <= hr <= high:
            r -= 1

        # Case B: both sides need to go higher than current high
        elif hl > high and hr > high:
            # Increase high minimally and move that side inward
            if hl < hr:
                high = hl
                l += 1
            else:
                high = hr
                r -= 1

        # Case C: both sides need to go lower than current low
        elif hl < low and hr < low:
            # Decrease low minimally (toward the closer demand) and move that side
            if hl > hr:
                low = hl
                l += 1
            else:
                low = hr
                r -= 1

        # Case D: conflicting requirements
        else:
            sys.stdout.write("NO\n")
            return

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


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

This implements the O(n) two-pointer + feasible-interval method that correctly handles negative heights and detects when synchronization becomes impossible.
