计算 A[i] 最右或最左且为 max 的段数

Question

给你一个包含N整数的数组，你必须回答K查询。每个查询都包含一个整数X，它是数组的（从 1 开始的索引）元素的索引。
为每个查询计算以下内容：

The number of segments containing the index X as the leftmost or the 
rightmost element and the number at the index `X` is `>=` each element
of that segment.

段形成示例：
您有 array {1, 2, 3}。可能的线段3是[2,3]和[1,2,3]和[3]。
2 的可能部分是[2]，[1,2]
我通过暴力得到了解决方案。最坏情况的时间复杂度是O(n * k)

Input: Array[] = {4,2,1,3}, Queries[] = {1,4}
Output:  
4  
3

Explanation: 
For first query 1 all possible valid segments are [4], [4,2] , [4,2,1] and [4,2,1,3] 
hence answer is 4.  
For second query 4 all possible valid segments are [3], [1,3] and [2,1,3]
hence answer is 3.

Answer 1

预处理 中的两个数组O(n)，其中元素是原始数组中每个元素的下一个较大元素的索引（一个在右侧，一个在左侧）。然后回答 中的每个查询O(1)。