10835: ABC152 - C - Low Elements
[Creator : ]
Description
Given is a permutation $P_1, \ldots, P_N$ of $1, \ldots, N$. Find the number of integers $i$ $(1 \leq i \leq N)$ that satisfy the following condition:
- For any integer $j$ $(1 \leq j \leq i)$, $P_i \leq P_j$.
- For any integer $j$ $(1 \leq j \leq i)$, $P_i \leq P_j$.
Input
Input is given from Standard Input in the following format:
```
$N$
$P_1$ $...$ $P_N$
```
```
$N$
$P_1$ $...$ $P_N$
```
Output
Print the number of integers $i$ that satisfy the condition.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $P_1, \ldots, P_N$ is a permutation of $1, \ldots, N$.
- All values in input are integers.
- $P_1, \ldots, P_N$ is a permutation of $1, \ldots, N$.
- All values in input are integers.
Sample 1 Input
5
4 2 5 1 3
Sample 1 Output
3
$i=1$, $2$, and $4$ satisfy the condition, but $i=3$ does not - for example, $P_i > P_j$ holds for $j = 1$.
Similarly, $i=5$ does not satisfy the condition, either. Thus, there are three integers that satisfy the condition.
Sample 2 Input
4
4 3 2 1
Sample 2 Output
4
All integers $i$ $(1 \leq i \leq N)$ satisfy the condition.
Sample 3 Input
6
1 2 3 4 5 6
Sample 3 Output
1
Only $i=1$ satisfies the condition.
8
5 7 4 2 6 8 1 3
4
Sample 4 Input
1
1
Sample 4 Output
1