Given a permutation of number from 1 to N. Among all the subarrays, find the number of unique pairs (a,b) such that a≠b and a is maximum and b is second maximum in that subarray.
Input Format
First line contains an integer, N.
Second line contains N space separated distinct integers, Ai, denoting the permutation.
Constraints
1≤N≤10^5
1≤Ai≤N
Output Format
Print the required answer.
Sample Input 0
5
1 2 3 4 5
Sample Output 0
4
Explanation 0
All possible subarrays are :
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
2
2 3
2 3 4
2 3 4 5
3
3 4
3 4 5
4
4 5
5
The 4 unique pairs are :
(2, 1)
(3, 2)
(4, 3)
(5, 4)
#include<bits/stdc++.h>
#define ll long long int
#define vii vector<int>::iterator
#define vli vector<ll>::iterator
#define vi vector<int>
#define vl vector<ll>
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x,y) make_pair(x,y)
#define MOD 1000000007
#define in cin>>
#define i2(x,y) cin>>x>>y
#define i3(x,y,z) cin>>x>>y>>z
#define os(x) cout<<x<<' '
#define on(x) cout<<x<<endl
#define o2(x,y) cout<<x<<' '<<y<<endl
#define o3(x,y,z) cout<<x<<' '<<y<<' '<<z<<endl
#define pn cout<<endl
#define F first
#define S second
#define for_it(it, X) for (__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++)
#define op(X) cout<<X.F<<" "<<X.S<<" ";
#define opn(X) cout<<X.F<<" "<<X.S<<endl;
#define SET(X,Y) memset(X,Y,sizeof(X))
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int t,i,j,k,n,m,a,b,c;
in n;
vi arr(n);
vector< pair<int,int> > chk;
for(i=0;i<n;i++)
{
in j;
chk.pb(mp(j,i+1));
}
sort(chk.rbegin(),chk.rend());
int l,r;
l = r = chk[0].S;
int ans = 0;
for(i=0;i<n;i++)
{
c=2;
if(chk[i].S <= l )
{
l = chk[i].S;
c--;
}
if(chk[i].S >= r )
{
r = chk[i].S;
c--;
}
ans+=c;
}
on(ans);
}
