#P2778. [2024名校noip模拟题]信号传递

[2024名校noip模拟题]信号传递

题目描述

Berland 的首都被 nn 座山峰包围,形成一个圆圈。

每座山的山顶都有一个瞭望塔,瞭望塔有高度的区别。

如果存在连接两座山峰 AA 和 BB 的弧上没有严格比 AA 或 BB 高的塔,那么 AA 和 BB 可以直接传达信息。

输入格式

第一行一个整数 nn,表示有多少座山。 第二行 nn 个整数 h1...nh_{1...n},依次表示每个瞭望塔的高度。

输出格式

输出一行一个整数,表示有多少对瞭望塔可以直接互相传递信息。

5
1 2 4 5 3
7

数据规模与约定

对于 100%100\% 的数据,1≤n≤1061\leq n\leq 10^6,1≤hi≤1091\leq h_i\leq 10^9。