<|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]\)**.

   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”) fails when the polyline goes below the start level; 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 (detailed comments)

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

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

    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];

    // Two pointers: l from the left, r from the right (0-based)
    int l = 0, r = n - 1;

    // Feasible synchronized height interval [low, high].
    // Invariant: using only already-reached parts of the polyline,
    // both climbers can stand at any common height in [low, high].
    int low = 0, high = 0;

    while (l < r) {
        // Next candidate vertices if we move one step inward.
        int hl = h[l + 1];
        int hr = h[r - 1];

        // Case A1: left can advance safely without changing [low, high]
        if (low <= hl && hl <= high) {
            l++;
        }
        // Case A2: right can advance safely without changing [low, high]
        else if (low <= hr && hr <= high) {
            r--;
        }
        // Case B: both next heights are above current high => must raise high
        else if (hl > high && hr > high) {
            // Raise to the smaller "required" height and move that side.
            if (hl < hr) {
                high = hl;
                l++;
            } else {
                high = hr;
                r--;
            }
        }
        // Case C: both next heights are below current low => must lower low
        else if (hl < low && hr < low) {
            // Lower to the larger (closer) "required" height and move that side.
            if (hl > hr) {
                low = hl;
                l++;
            } else {
                low = hr;
                r--;
            }
        }
        // Case D: incompatible constraints => cannot keep equal height
        else {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";
    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.