少见的思维难题。
30%
N^2暴力解决。
60%
各种神奇乱搞。
100%
分治。
假设我们分到的区间为[l,r]，中点为mid，可以考虑计算l~mid和mid+1~r的方案，加上穿过mid和mid+1的方案，就是整个区间的方案数。
枚举左端点i，如果直接枚举右端点就又是N^2。
所以不能直接枚举。
左边=l~mid
右边=mid+1~r
设u、v，分别表示右边第一个比左边最大值大的位置，和第一个比左边最小值小的位置。
如果没有这样的数就设为r+1。 
分段考虑。
第一段mid+1~u-1
因为还没有过u和v，所以此时的最大值一定在左边。
这一段的总和为
左最大值 * 左最小值 * 个数(u-mid-1)
第二段u~v-1
因为已经过了u，所以最大值在右边。
但是我们不知道具体的最大值。
因为左最小值相同，所以可以用乘法分配律，前缀和乱搞。
这一段的总和为
右最大值和*左最小值
第三段v~r
此时，最大和最小值都在左边。
但是我们都不知道具体数目，只能暴力解决，把每个位置的最大*最小相加。
当然我们也可以用前缀和。
注意事项
如果u>=v，那就大致和上面相同，只是一些地方反过来。
算完一段后，分成两段继续分治就行了。