Background

Translated from ROI 2018 Day2 T1. Расшифровка (Decryption).

Problem Description

Research shows that the order of Chinese characters does not necessarily affect reading. Scientists have done similar research on sequences.

Given a positive integer sequence, if the first element is the minimum among all numbers in the sequence, and the last element is the maximum among all numbers in the sequence, then we call it a correct sequence. For example, the sequences $[1, 3, 2, 4]$ and $[1, 2, 1, 2]$ are correct, but the sequence $[1, 3, 2]$ is not.

You are given a sequence of length $n$: $[a_1, a_2, \ldots, a_n]$. For a segment of this sequence $[a_l, a_{l+1}, \ldots, a_r]$, if the first element of the segment is the minimum within the segment, and the last element of the segment is the maximum within the segment, then we call it a correct segment.

For the given sequence, find the minimum number of segments it must be split into so that every segment is a correct segment. The sequence $[2, 3, 1, 1, 5, 1]$ can be split into three correct segments: $[2, 3]$, $[1, 1, 5]$, and $[1]$.

Write a program that, in the given order, determines the minimum number of correct segments.

Input Format

The first line contains an integer $n$.

The next line contains $n$ numbers: $a_1, a_2, \ldots, a_n$.

Output Format

Output the minimum number of segments that the sequence can be split into.

5
5 4 3 2 1

5

4
1 3 2 4

1

6
2 3 1 1 5 1

3

Hint

• Subtask 1 (30 points): $1 \leq n \leq 500$.
• Subtask 2 (30 points): $1 \leq n \leq 5000$.
• Subtask 3 (40 points): $1 \leq n \leq 3 \times 10^5$.

Constraints: For all testdata, $1 \leq n \leq 3 \times 10^5$, and $1 \leq a_i \leq 10^9$.

Translated by ChatGPT 5