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<sup class="upper-index">6</sup>), *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<sup class="upper-index">9</sup>.

class Deque(object):
    def __init__(self, size):
        self._deque = [None]*size
        self._front = 0
        self._end = 0

    def front(self):
        return self._deque[self._front]

    def front_index(self):
        return self._front

    def end(self):
        return self._deque[self._end-1]

    def end_index(self):
        return self._end

    def get(self, index):
        return self._deque[index]

    def pop(self):
        x = self.get(self._front)
        self._front += 1
        return x

    def push(self, x):
        self._deque[self._end] = x
        self._end += 1

    def is_empty(self):
        return self._front >= self._end

    def __repr__(self):
        return " ".join([str(x) for x in self._deque[self._front: self._end]])


class RSDeque(Deque):
    """Reversed Sorted Deque
    [5,3,2] push 4 -> [5,4]
    [5,4,3] push 3 -> [5,4,3,3]
    [5,3,2] pop -> [3,2]

    cmp(x, y): comparison function
        x > y, return 1
        x = y, return 0
        x < y, return -1
    """
    def __init__(self, size, cmp):
        super(RSDeque, self).__init__(size)
        self.cmp = cmp

    def push(self, x):
        while not self.is_empty() and self.cmp(self.end(), x) < 0:
            self._end -= 1
        super(RSDeque, self).push(x)

    def bisect_left(self, x):
        # if all items > x, return -1
        # find the leftmost y where y<=x, return the index of y
        left, right = self._front, self._end-1
        while left <= right:
            mid = (left + right) >> 1
            if self.cmp(self.get(mid), x) <= 0:
                right = mid-1
            else:
                left = mid+1
        return left if left < self._end else -1

    def bisect_rightmost(self, x, cmp):
        # find the rightmost y where y<=x, return the index of y
        # assuming deque is ordered by key ascendingly
        left, right = self._front, self._end-1
        while left <= right:
            mid = (left + right) >> 1
            if cmp(self.get(mid), x) <= 0:
                left = mid+1
            else:
                right = mid-1
        return right if right < self._end else -1


class Height(object):
    def __init__(self, height, index):
        self.height = height
        self.index = index

    def __repr__(self):
        return "position: " + str(self.index) + " height: " + str(self.height)


def height_cmp(h1, h2):
    if h1.height == h2.height:
        return 0
    return -1 if h1.height < h2.height else 1


def input_data():
    n = int(input().strip())
    heights = list(map(int, input().strip().split()))
    return n, heights


def find_leftmost_hill(deq, h):
    p0 = deq.bisect_left(h)
    # all hills in deque > h, only the last hill can be watched
    if p0 < 0:
        return deq.end_index()-1
    else:
        # all hills in deque <= h, so all hills can be watched
        if p0 <= deq.front_index():
            return deq.front_index()
        # hills in deque [p0:end] <= h, so these hills can be
        # watched, and plus the hill before deque[p0] i.e. deque[p0-1]
        else:
            return p0-1


def index_cmp(h1, h2):
    if h1.index == h2.index:
        return 0
    return -1 if h1.index < h2.index else 1


def find_rightmost_hill(deq, preIndex):
    h0 = Height(0, preIndex)
    p0 = deq.bisect_rightmost(h0, index_cmp)
    #print("h0=", h0.index, "p0=", p0)
    if p0 < 0:
        return deq.front_index()-1
    else:
        if deq.get(p0).index == h0.index:
            return p0-1
        return p0


def solve_prob(n, heights):
    deq = RSDeque(3*n, height_cmp)
    # pre[i]: the leftmost hill can be watched by height[i]
    pre = [0] + [(i-1) for i in range(1, n)]

    ans = 0
    # 1st scan
    for i in range(n):
        h = Height(heights[i], i)
        #print("1st scan, i=", i, "h=", h.height)
        if not deq.is_empty():
            p = find_leftmost_hill(deq, h)
            watchedNum = deq.end_index() - p
            pre[h.index] = deq.get(p).index
            ans += watchedNum
            #print("deq=", str(deq))
            #print("p=", p)
            #print("ans +=", watchedNum)

        # push current hill to deque
        deq.push(h)

    #print("pre=", pre)

    def get_index(n, index):
        return index if index < n else index - n

    # 2nd scan
    for i in range(n):
        h = Height(heights[i], i+n)
        #print("2nd scan, i=", i, "h=", h.height)
        #print("deq0=", str(deq))
        # to avoid duplicating
        while not deq.is_empty() and pre[get_index(n, deq.front().index)] <= i:
            deq.pop()
        #print("deq1=", str(deq))
        if not deq.is_empty():
            p = find_leftmost_hill(deq, h)
            q = find_rightmost_hill(deq, pre[i]+n)
            if q >= p:
                ans += q-p+1
                #print("ans +=", q-p+1)
            #print("p=", p, "q=", q)
        deq.push(h)

    print(ans)


if __name__ == "__main__":
    n, heights = input_data()
    solve_prob(n, heights)
