← 返回题目列表

Codeforces · 5/E

E. 宾电信号

中文机器翻译题面 查看原题

大家都知道,很久以前,在现在的贝尔兰德境内,居住着宾迪亚部落。他们的首都被n座山丘包围,形成一个圆圈。每座山上都有一名看守人,日夜监视着附近地区。

如果出现任何危险,看守人可以在山上生火。如果在连接两座山的圆弧上没有任何一座山比这两座山更高,则一个守望者可以看到另一个守望者的信号。对于任意两座山,都有两条不同的圆弧连接,只要其中至少一条圆弧满足上述条件,即可看到信号。例如,对于任何两个相邻的守望者,其中一个的信号确实会被另一个看到。

该值班系统的一个重要特征是能够看到彼此信号的成对值班人员的数量。你需要根据给定的山丘高度来找到这个数字。

输入

输入数据的第一行包含一个整数n(3≤n≤106),n——首都周围山丘的数量。第二行包含 n 个数字——按顺时针顺序排列的山丘高度。所有身高数字均为整数,且介于 1 到 109 之间。

输出

打印所需数量的对。

示例

输入 #1

5
1 2 4 5 3

输出 #1

7