Overview

This is a problem of counting the number of points (peaks) in a sequence that are strictly higher than both of their neighbors.

Analysis

This problem is very straightforward — we simply need to check each point one by one to see whether it satisfies the “peak” condition.

Understanding the definition of a peak precisely:

A point \(i\) is a peak if it satisfies both of the following conditions simultaneously: - \(A_{i-1} < A_i\) (strictly higher than the left neighbor) - \(A_i > A_{i+1}\) (strictly higher than the right neighbor)

Verification with a concrete example:

For example, if the elevation data is 1 3 2 4 1 with \(N = 5\):

Point \(i\)	\(A_{i-1}\)	\(A_i\)	\(A_{i+1}\)	Peak?
2	1	3	2	✅ (\(1 < 3\) and \(3 > 2\))
3	3	2	4	❌ (\(3 < 2\) does not hold)
4	2	4	1	✅ (\(2 < 4\) and \(4 > 1\))

Therefore, the number of peaks is 2.

Notes: - The first point (\(i = 1\)) and the last point (\(i = N\)) cannot be peaks because they do not have both neighbors. - Be careful that equality (\(=\)) does not qualify as a peak. The conditions require strict inequalities.

In this problem, \(N \leq 2 \times 10^5\), so a simple \(O(N)\) approach that examines each point once is fast enough. No special algorithms or data structures are needed.

Algorithm

1. Read \(N\) and the elevation array \(A\) from input.
2. Initialize a counter count to \(0\).
3. For \(i = 1, 2, \ldots, N-2\) (0-indexed), check the following:
   • If \(A[i-1] < A[i]\) and \(A[i] > A[i+1]\), increment count by \(1\).
4. Output count.

※ In the problem statement, we check \(i = 2, 3, \ldots, N-1\) using 1-indexed notation, which corresponds to \(i = 1, 2, \ldots, N-2\) in Python’s 0-indexed notation.

Complexity

• Time complexity: \(O(N)\) — We only need a single pass through the array.
• Space complexity: \(O(N)\) — We store the elevation data as an array.

Implementation Notes

• Python’s range(1, N - 1) generates values from \(1\) to \(N - 2\), which naturally excludes the first and last points.

• In the condition check, use < and > instead of <=, and make sure not to forget that the inequalities must be strict.

  Source Code

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(1, N - 1):
    if A[i - 1] < A[i] and A[i] > A[i + 1]:
        count += 1
print(count)

---

This editorial was generated by claude4.6opus-thinking.