E. Bindian Signalizing （拆环成链）（好题）

​​点击打开链接​​

​​http://codeforces.com/contest/5/problem/E​​

E. Bindian Signalizing

Everyone knows that long ago on the territory of present-day Berland there lived Bindian tribes. Their capital was surrounded by n

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 nnumbers — 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      

题意：就是这些数形成一个环，问你两个数之间的数都少于这两个数的pair有多少对？

比如样例：

1 2

1 3

2 4

4 5

3 1 2

3 1 2 4

5 3 1 2 4

一共7个。

题解：

先要把环拆成链，将山的序列改变，第一座山是最高的山。 

其次是统计对于这个序列的L数组和R数组。表示：

L[i]表示i左侧比第一个比 i 高(或等)的位置。

R[i]表示i右侧第一个比 i 高(或等)的位置。

C[i]表示从i到 R[i]的左开右闭区间内高度等于i的山的数目。

其中，L和 R是位置，而 C是数目。

那么对于一座山i而言，它可以和 L[i] 和 R[i]都构成能互相看见的pair，并且和i到 R[i]之间所有高度等于 i 的山构成能互相看见的pair。

所以问题就是计算 L数组、R数组和 C数组。

L[i]==0 && R[i]==N 时只需要算一个ans,因为重复了 。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000010;
int H[maxn], L[maxn], R[maxn], C[maxn];
int n;

int main()
{
    scanf("%d",&n);  
    for (int i = 0; i < n; i++)
    {
        scanf("%d",&H[i]);//不取消同步的cin会T 
    }                
    rotate(H, max_element(H, H + n), H + n);
    //5 3 1 2 4
    H[n] = H[0];
    for (int i = n - 1; i >= 0; --i)
    {
        R[i] = i+1;
        while(R[i] < n && H[R[i]] < H[i])
        {
            R[i] = R[R[i]];
        }   
         
        if (R[i] < n && H[R[i]] == H[i])
        {
            C[i] = C[R[i]] + 1;
            R[i] = R[R[i]];
        }
        
    }
    //for(int i=0;i<=n;i++)printf("L[%d]=%d ",i,L[i]);cout<<endl;
    //for(int i=0;i<=n;i++)printf("R[%d]=%d ",i,R[i]);cout<<endl;
    //for(int i=0;i<=n;i++)printf("C[%d]=%d ",i,C[i]);cout<<endl;
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        ans += C[i];
        if (H[i] == H[0]) continue;
        
        L[i] = i - 1;
        while(L[i] > 0 && H[L[i]] <= H[i])
        {
            L[i] = L[L[i]];
        }
        ans += 2;
        if (L[i] == 0 && R[i] == n)
        {
            ans--;
        }
    }
    //for(int i=0;i<=n;i++)printf("L[%d]=%d ",i,L[i]);cout<<endl;
    printf("%I64d\n",ans);
    return 0;
}