#include <bits/stdc++.h> 
using namespace std;
#define lb (id&-id)
#define int long long
int a[1000010],b[1000010],c[1000010],mn[1000010];
void insert(int id){
	while (id<=1000005){
		c[id]++; id+=lb;
	}
}int ask(int id){
	int ans=0;
	while (id>0) ans+=c[id],id-=lb;
	return ans;
}signed main(){
	set<int> st; map <int,int> mp; st.insert(1e18);
	int n,tot=0,ans=1e18,sta=1,mx=0; cin>>n;
	for (int i=1; i<=n; i++){
		cin>>a[i]; b[i]=a[i];
		st.insert(a[i]);
	}sort(b+1,b+n+1); mn[n+1]=1e18; b[n+1]=1e18;
	for (auto x:st) mp[x]=++tot;
	for (int i=n; i>=1; i--){
		mn[i]=min(mn[i+1],a[i]);
	}for (int i=1; i<=n+1; i++){
		if (a[i]!=b[i]){
			if(a[i-1]==b[i-1]&&mx<=mn[i])
			ans=min(ans,(sta-1)*(sta-1)+(n-i+1)*(n-i+1)); 
			sta=i+1; 
		}mx=max(mx,a[i]);
	}for (int i=1; i<=n; i++){
		insert(mp[a[i]]);
		int l=0,r=i;
		while (l<r-1){
			int mid=(l+r)/2;
			if (ask(mp[b[mid]])>=mid) l=mid;
			else r=mid;
		}if (ask(mp[b[r]])>=r) ans=min(ans,i*i+(n-r)*(n-r));
		else if (ask(mp[b[l]])>=l) ans=min(ans,i*i+(n-l)*(n-l));
	}memset(c,0,sizeof(c));
	reverse(a+1,a+n+1);
	for (int i=1; i<=n; i++){
		insert(n-mp[a[i]]+1);
		int l=0,r=i;
		while (l<r-1){
			int mid=(l+r)/2;
			if (ask(n-mp[b[n-mid+1]]+1)>=mid) l=mid;
			else r=mid;
		}if (ask(n-mp[b[n-r+1]]+1)>=r) ans=min(ans,i*i+(n-r)*(n-r));
		else if (ask(n-mp[b[n-l+1]]+1)>=l) ans=min(ans,i*i+(n-l)*(n-l));
	}cout<<ans;
	
	return 0;
}