Overview

For each point, check whether it is higher than both its left and right neighbors, and count the number of points that satisfy this condition. Since only points that have both neighbors can be mountain tops, you can find the answer by checking each point in order, excluding the first and last.

Analysis

The definition of a mountain top is that point \(i\) simultaneously satisfies:

• \(A_{i-1} < A_i\)
• \(A_i > A_{i+1}\)

In other words, you can determine this by looking at only the one point to the left and the one point to the right.

For example, given

\(A = [1, 3, 2, 4, 4, 1]\)

• \(i=2\) with value \(3\) is a mountain top because it is greater than \(1\) on the left and greater than \(2\) on the right
• \(i=3\) with value \(2\) is not a mountain top
• \(i=4\) with value \(4\) is not a mountain top because it is not strictly greater than \(4\) on the right

In this way, each point can be judged independently.

Key Observations

• Determining whether a point is a mountain top requires only 3 adjacent points
• The first point \(i=1\) and the last point \(i=N\) cannot be mountain tops because they lack a neighbor on one side
• Therefore, we only need to check from \(i=2\) to \(i=N-1\) in order

On the Naive Approach

In this problem, there is no need to examine a wide area around each point. If you were to think about whether “that point is higher than many surrounding points” and perform unnecessary comparisons, it would be wasteful, but in reality, checking just one point on each side is sufficient.

Therefore, it can be solved in \(O(N)\) with just a single pass through the array. Since \(N \leq 2 \times 10^5\), this method is fast enough.

Algorithm

1. Read \(N\) and array \(A\) from input
2. Initialize a variable cnt to \(0\) to represent the answer
3. Iterate from \(i=1\) to \(N-2\) (0-indexed)
4. If
   • \(A[i-1] < A[i]\)
   • \(A[i] > A[i+1]\)

are both satisfied, increment cnt by \(1\) 5. Output cnt at the end

When using a 0-indexed array, Python’s a[i] corresponds to \(A_{i+1}\) in the problem statement. Therefore, it is natural to write the loop as for i in range(1, n - 1):.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since the first and last points cannot be mountain tops, we only examine the middle points using range(1, n - 1).

• The condition requires being strictly higher, not just “higher”, so use < and > instead of <=.

• Since the input can be relatively large, using sys.stdin.buffer.read() provides a fast and stable implementation.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:1+n]
    
    cnt = 0
    for i in range(1, n - 1):
        if a[i - 1] < a[i] and a[i] > a[i + 1]:
            cnt += 1
    
    print(cnt)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.