思路:单调栈 + 枚举

使用单调栈来找到每个元素左右第一个比其大的元素索引。左侧数组 left 记录每个元素左边第一个大于它的元素索引，右侧数组 right 记录每个元素右边第一个大于它的元素索引。遍历每个元素，计算以该元素为唯一最大值的子数组数量，公式为 left_count * right_count，其中 left_count 是当前元素到左边界的距离，right_count 是当前元素到右边界的距离。最终汇总所有子数组数量。

代码

java

import java.util.Stack;

题目内容

小红有一个长度为n的数组{$a_1,a_2,...,a_n$},如果一个数组有一个唯一的最大值，那么这个数组就是一个好数组。

小红想知道这个数组有多少连续子数组是好数组。

连续子数组是指在原数组中，连续的选择一段元素组成的新数组。

输入描述

第一行输入一个整数$n$($1≤n≤10^5$)表示数组中的元素数量。 第二行输入$n$个整数$a_1,a_2,...,a_n$($1≤a_i≤10^9$)表示数组元素。

输出描述

在一行上输出一个整数，表示有多少连续子数组是好数组。

样例1

输入

5
1 2 5 4 5

输出

12

说明

一共有$15$个子数组，其中$[1,2,5,4,5],[2, 5,4, 5],[5,4,5]$不是好数组，因为最大值是$5$，不是唯一的。