#include<cstdio>#include <set>#include <cstring>#include <algorithm>#define maxn 1000010using namespace std;int b[maxn];int fa[maxn];int C[maxn];int a[maxn]; int n;int getfa(int x){ return fa[x] == x?x:fa[x] =getfa(fa[x]);}inline int lowbit(int x){ return x&-x;}int sum(int x){ int res = 0; while(x >0) { res += C[x]; x -= lowbit(x); } return res;}void add(int x){ while(x< maxn) { C[x]++; x += lowbit(x); }}int main(){ while(scanf("%d",&n) != EOF) { memset(C,0,sizeof C); for(int i = 1;i <= n;i++) { scanf("%d",&b[i]); a[i] = b[i]; fa[i] = i; } sort(b+1,b+1+n); for(int i = 1;i <= n;i++) a[i] = lower_bound(b+1,b+1+n,a[i])-b; for(int i = 1;i <= n;i++) { int fx = getfa(i); int fy = getfa(a[i]); if(fx != fy) { fa[fx] =fy; } } set<int > ans1; for(int i = 1;i <= n;i++) { ans1.insert(getfa(i)); } long long ans2 = 0; for(int i = 1;i <= n;i++) { ans2 += sum(maxn-1)-sum(a[i]); add(a[i]); } printf("%dn%lldn",n-ans1.size(),ans2); } return 0;}
