Codeforces Beta Round #5

Everyone knows that long ago on the territory of present-day Berland there lived Bindian tribes. Their capital was surrounded by n hills, forming a circle. On each hill there was a watchman, who watched the neighbourhood day and night.

In case of any danger the watchman could make a fire on the hill. One watchman could see the signal of another watchman, if on the circle arc connecting the two hills there was no hill higher than any of the two. As for any two hills there are two different circle arcs connecting them, the signal was seen if the above mentioned condition was satisfied on at least one of the arcs. For example, for any two neighbouring watchmen it is true that the signal of one will be seen by the other.

An important characteristics of this watch system was the amount of pairs of watchmen able to see each other's signals. You are to find this amount by the given heights of the hills.

Input

The first line of the input data contains an integer number n (3 ≤ n ≤ 106), n — the amount of hills around the capital. The second line contains n numbers — heights of the hills in clockwise order. All height numbers are integer and lie between 1 and 109.

Output

Print the required amount of pairs.

Examples

input

5
1 2 4 5 3

output

7
这个题的意思是两两之间不存在更大的数，类似单调栈思想，统计出每一个位置的贡献就好，但是他是一圈的，这个是真的厉害了，要先拆环为链，当然选择最高的
啊，然后用进行比较统计左右两边的贡献就可以了

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1e6+5;
LL a[N],b[N],l[N],r[N],ans,pos,n,c[N],ma;
int main() {
    scanf("%lld",&n);
    for (LL i=0; i<n; i++) {
        scanf("%lld",&a[i]);
        if (a[i]>ma) {
            ma=a[i];
            pos=i;
        }
    }
    pos--;
    for (LL i=1; i<=n; i++)
        b[i]=a[(pos+i)%n];
    l[1]=1;
    for (LL i=2; i<=n; i++) {
        l[i]=i-1;
        while (l[i]>1 && b[l[i]]<=b[i]) l[i]=l[l[i]];
    }
    for (LL i=n; i>=1; i--) {
        r[i]=i+1;
        while (r[i]<=n && b[r[i]]<b[i]) r[i]=r[r[i]];
        if (r[i]<=n && b[r[i]]==b[i]) {
            c[i]=c[r[i]]+1;
            r[i]=r[r[i]];
        }
    }
    LL ans=0;
    for (LL i=2; i<=n; i++) {
        ans+=c[i]+2;
        if (l[i]==1 && r[i]==n+1) ans--;
    }
    printf("%lld
",ans);
    return 0;
}

Codeforces Beta Round #5

相关推荐