#ABC152C. Low Elements

Low Elements

题目描述

Given is a permutation P1,,PNP_1, \ldots, P_N of 1,,N1, \ldots, N. Find the number of integers ii (1iN)(1 \leq i \leq N) that satisfy the following condition:

  • For any integer jj (1ji)(1 \leq j \leq i), PiPjP_i \leq P_j.

给定的是 1,,N1, \ldots, N 的排列 P1,,PNP_1, \ldots, P_N 。求满足以下条件的整数 ii (1iN)(1 \leq i \leq N) 的个数。 (1iN)(1 \leq i \leq N) 满足以下条件的整数个数:

  • 对于任意整数 jj (1ji)(1 \leq j \leq i) , jj (1ji)(1 \leq j \leq i) , jj (1ji)(1 \leq j \leq i) (1ji)(1 \leq j \leq i) , PiPjP_i \leq P_j .

输入格式

输入内容按以下格式标准输入:

NN
P1P_1 ...... PNP_N

输出格式

打印满足条件的整数 ii 的个数。

样例 #1

样例输入 #1

5
4 2 5 1 3

样例输出 #1

样例 #2

样例输入 #2

4
4 3 2 1

样例输出 #2

样例 #3

样例输入 #3

6
1 2 3 4 5 6

样例输出 #3

说明

数据规模与约定

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • P1,,PNP_1, \ldots, P_N1,,N1, \ldots, N 的排列。
  • 所有输入值均为整数。

样例 11 解释

i=1i=12244 满足条件,但 i=3i=3 不满足,例如, Pi>PjP_i \gt P_jj=1j = 1 成立。
同样, i=5i=5 也不满足条件。因此,有三个整数满足条件。

样例 22 解释

所有整数 ii (1iN)(1 \leq i \leq N) 满足条件。

样例 33 解释

只有 i=1i=1 满足条件。

样例 #4

样例输入 #4

8
5 7 4 2 6 8 1 3

样例输出 #4

样例 #5

样例输入 #5

1
1

样例输出 #5