CF5E.Bindian Signalizing

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.

众所周知，很久以前，在如今贝尔兰（Berland）的领土上生活着宾迪安（Bindian）部落。他们的首都被 $n$ 座山丘环绕，这些山丘构成一个圆圈。每座山丘上都有一名守望者，日夜监视着周围的区域。

一旦发生危险，守望者便可在其所在的山丘上点燃烽火。一名守望者能够看见另一名守望者的信号，当且仅当：在连接这两座山丘的圆弧上，不存在任何一座山丘的高度严格高于这两座山丘中的任意一座。由于任意两座山丘之间存在两条不同的圆弧，因此只要上述条件在其中至少一条圆弧上成立，信号即被视为可被看见。例如，对于任意两名相邻的守望者，总有一方能看见另一方发出的信号。

该警戒系统的一个重要特征，是能够相互看见对方信号的守望者对的数量。现给定各山丘的高度，请你计算出这一数量。

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.

输入数据的第一行包含一个整数 $n$（$3 \leq n \leq 10^6$），其中 $n$ 表示首都周围山丘的数量。第二行包含 $n$ 个数字，表示按顺时针顺序排列的各山丘的高度。所有高度值均为整数，且在 $1$ 到 $10^9$ 之间。

Print the required amount of pairs.

输出所需的数对数量。