思路：单调栈

对于一个值$x$，我们需要找到其两边比$x$大的第一个值。

使用单调递减栈可以实现该目标。栈中每个元素的左边是比该元素大的第一个值。而当一个元素出栈时，那么其右边第一个比其大的值也就找到了。

时间复杂度为$O(N)$

题目描述

小友正在优化财务报表分析功能。给定一个由不同整数构成的数组revenues，每个元素表示在不同时间段内的收入。我们用以下方式定义一个与revenues长度相同的数组maxDurations:

$maxDurations[i]$是一个子数组 $revenues[l..r]$的最大长度，该子数组中的最大收入等于$revenues[i]$。

返回数组 maxDurations。

注意，子数组是数组的连续部分。

输入描述

第一行输入$N$，表示数组的长度

输入长度为$N$的数组的各个元素

输出描述

maxDurations

样例

输入

6
1 3 2 4 3 5

输出

1 3 1 5 1 6

说明

对于 revenues[0]，最长的子数组，其中最大值为 1，是 nums[0..0]，所以 maxDurations[0]=1。
对于 revenues[1]，最长的子数组，是 revenues[0..2]，其中最大值为 3，所以 maxDurations[1]= 3。
对于 revenues[2]，最长的子数组，是 revenues[2..2]，其中最大值为 2，所以 maxDurations[2]=1.
对于 revenues[3]，最长的子数组，是revenues[0..4]，其中最大值为4，所以maxDurations[3]=5
对于 revenues[4]，最长的子数组，是 nums[4..4]，其中最大值为 3，所以 maxDurations[4]=1
对于 revenues[5]，最长的子数组，是 nums[0..5]，其中最大值为5，所以 maxDurations[5]=6。