题目描述
Given is a permutation P1,…,PN of 1,…,N. Find the number of integers i (1≤i≤N) that satisfy the following condition:
·For any integer j (1≤j≤i), Pi≤Pj.
Constraints
·1≤N≤2×105
·P1,…,PN is a permutation of 1,…,N.
·All values in input are integers.
输入
Input is given from Standard Input in the following format:
N
P1 … PN
输出
Print the number of integers i that satisfy the condition.
样例输入 Copy
【样例1】 5 4 2 5 1 3 【样例2】 4 4 3 2 1 【样例3】 6 1 2 3 4 5 6 【样例4】 8 5 7 4 2 6 8 1 3 【样例5】 1 1
样例输出 Copy
【样例1】 3 【样例2】 4 【样例3】 1 【样例4】 4 【样例5】 1
提示
样例1解释
i=1, 2, and 4 satisfy the condition, but i=3 does not - for example, Pi>Pj holds for j=1.
Similarly, i=5 does not satisfy the condition, either. Thus, there are three integers that satisfy the condition.
样例2解释
All integers i (1≤i≤N) satisfy the condition.
样例3解释
Only i=1 satisfies the condition.
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma comment(linker, "/stack:200000000") #pragma GCC optimize (2) #pragma G++ optimize (2) #include <bits/stdc++.h> #include <algorithm> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define wuyt main typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} //#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) //char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll inf = 1e15; const int maxn = 2e5 + 7; const int mod = 1e9 + 7; #define start int wuyt() #define end return 0 int cnt; start{ int n=read; int minn=mod; for(int i=1;i<=n;i++){ int num=read; minn=min(num,minn); if(minn==num) cnt++; } cout<<cnt<<endl; end; } /************************************************************** Language: C++ Result: 正确 Time:24 ms Memory:2024 kb ****************************************************************/
