Overview

Given elevation data for \(N\) points, the problem asks us to count how many points have elevation strictly higher than both neighboring points (“peaks”).

Analysis

The definition of a “peak” is that the elevation \(A_i\) at a point \(i\) is greater than both the elevation \(A_{i-1}\) of its left neighbor and the elevation \(A_{i+1}\) of its right neighbor. In other words, it satisfies \(A_{i-1} < A_i\) and \(A_i > A_{i+1}\).

The key points for solving this problem are as follows: - Range of evaluation: Only points in the range \(1 < i < N\) (from the 2nd to the \((N-1)\)-th point), where both neighbors exist, can be peaks. - Complexity: The number of points \(N\) is at most \(2 \times 10^5\). Since comparing each point with its two neighbors takes constant time, checking sequentially from one end to the other easily fits within the time limit.

For example, if the elevations are [1, 3, 2, 4, 1]: - The 2nd element “3”: since 1 < 3 and 3 > 2, it is a peak. - The 3rd element “2”: since 3 > 2 and 2 < 4, it is not a peak. - The 4th element “4”: since 2 < 4 and 4 > 1, it is a peak. In this way, a straightforward approach of checking the condition one by one leads to the correct answer.

Algorithm

1. Read the list of elevations \(A\).
2. Initialize a variable count to 0 to record the number of peaks.
3. Iterate index \(i\) from 1 to \(N-2\) (in 0-indexed terms, from the 2nd element to the \((N-1)\)-th element), performing the following check:
   • If \(A_{i-1} < A_i\) and \(A_i > A_{i+1}\), increment count by 1.
4. Output the final value of count.

Complexity

• Time complexity: \(O(N)\)
  • Since we only scan the list once, the computation finishes in time proportional to the number of points \(N\).
• Space complexity: \(O(N)\)
  • Memory is needed to store the input elevation data in a list.

Implementation Notes

• Index range: By using Python’s range(1, n - 1), we can efficiently loop over exactly from the “2nd element” to the “second-to-last element”.

• Comparison operators: In Python, it is possible to chain comparison operators like \(A_{i-1} < A_i > A_{i+1}\), but for code readability, it is common practice to explicitly separate the conditions using and.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    a = list(map(int, input_data[1:]))
    
    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)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.