Bindian Signalizing

题意翻译

**题面大意** 给定一个圆和圆弧上的 $n$ 座山，每座山上有一名看守员，若连接两名看守员的圆弧（注：圆弧有左右两条，任意一条满足即可）两条中没有比（这两个看守员所在的）两座山更高的山，则这两名看守人彼此能看到各自的信号。现在给定 $n$ 座山的高度，求能够看到彼此信号的成对看守人的数量 **输入格式** 输入数据的第一行包含一个整数 $n$（$3\le n\le10^6$），表示该圆圈上的山丘数量。 第二行包含 $n$ 个数字整数表示山的高度（按顺时针顺序排列）。所有的高度介于 $1$ 和 $10^9$ 之间 **输出格式** 一个整数，表示答案

题目描述

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.

输入输出格式

输入格式

The first line of the input data contains an integer number $ n $ ( $ 3<=n<=10^{6} $ ), $ 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 $ 10^{9} $ .

输出格式

Print the required amount of pairs.

输入输出样例

输入样例 #1

5
1 2 4 5 3

输出样例 #1

7