#abc152c. [abc152_c]Low Elements

[abc152_c]Low Elements

题目描述

给定一个1,ldots,N1, \\ldots, N的排列P1,ldots,PNP_1, \\ldots, P_N。找到满足以下条件的整数ii (1leqileqN)(1 \\leq i \\leq N) 的数量:

  • 对于任何整数jj (1leqjleqi)(1 \\leq j \\leq i),有PileqPjP_i \\leq P_j

约束条件

  • 1leqNleq2times1051 \\leq N \\leq 2 \\times 10^5
  • P1,ldots,PNP_1, \\ldots, P_N1,ldots,N1, \\ldots, N的排列。
  • 输入中的所有值都是整数。

输入

从标准输入读入数据,格式如下:

NN P1P_1 ...... PNP_N

输出

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


示例输入 1

5
4 2 5 1 3

示例输出 1

3

i=1i=12244满足条件,但i=3i=3不满足条件 - 例如,对于j=1j=1,有Pi>PjP_i > P_j
同样地,i=5i=5也不满足条件。因此,满足条件的整数有三个。


示例输入 2

4
4 3 2 1

示例输出 2

4

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


示例输入 3

6
1 2 3 4 5 6

示例输出 3

1

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


示例输入 4

8
5 7 4 2 6 8 1 3

示例输出 4

4

示例输入 5

1
1

示例输出 5

1