Query on Queues

You're given an array containing N integers and you have to answer K queries. Each query contains an integer X which is the index of the i th ( 1 based index) element of the queue

Write a program to determine the following for each query

• 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 the first segment.

Example
Segment formation : You have 3 numbers 1, 2 and 3
The possible segments for 3 are [3], [3,2], [3,2,1]
The possible segments for 2 are [2], [2,1]

Input Format

• First line : Two space seperated integers N and K
• Second line : N space seperated integers ( denoting the elements of the queue)
• Next K lines is the value of X

Function description

• N : represents the size of array
• A : represents the array
• K : represents the size of queries
• Q : represents the queries

Constrains

• 1 <= N,K <= 10^5
• 1 <= Each element of the queue <= 10^9
• 1 <= X <= N

Sample Input

Sample input 1
4 2
4 2 1 3
1
4

Sample output 1
4
3

Sample input 2
5 2
4 2 3 5 1
1
3

Sample output 2
3
2

I've solved this question by getting the number of consecutive smaller elements on the right and left side of the given index for each query.
But this approach takes O(N*K) time complexity.

Can someone please suggest a better solution for this with lesser time complexity ?

public int[] solve(int N, int[] A, int K, int[] Q)
{
		//Your solution here
}

Edit : Solved this solution by precomputing the index of greatest element in right side and left side

public int[] solve(int N, int[] A, int K, int[] Q)
{
	int len = N;
	int[] left = new int[len];
	int[] right = new int[len];
	Stack<Integer> stack = new Stack<>();
	Arrays.fill( left, -1);
	Arrays.fill( right, -1);
	for( int i= len-1; i >= 0; i--) {
		if( !stack.isEmpty()) {
			while( !stack.isEmpty() && A[stack.peek()] <= A[i] ) {
				stack.pop();
			}
		}
		right[i] = stack.isEmpty() ? -1 : stack.peek();
		stack.push(i);
	}
	stack.clear();
	for( int i= 0; i < len; i++) {
		if( !stack.isEmpty()) {
			while( !stack.isEmpty() && A[stack.peek()] <= A[i] ) {
				stack.pop();
			}
		}
		left[i] = stack.isEmpty() ? -1 : stack.peek();
		stack.push(i);
	}
	int[] result = new int[K];
	for(int i=0; i<K; i++ )
	{
		int ans = 0;
		int index = Q[i]-1;
		if( left[index] != -1)
		{
			ans += Math.abs( index - left[index]) -1;
		}
		else
		{
			ans += Math.abs( index );
		}
		if( right[index] != -1)
		{
			ans += Math.abs( index - right[index]) -1;
		}
		else
		{
			ans += Math.abs(index - len)-1;
		}
		ans++;
		result[i] = ans;
	}
	return result;
}

Credits for solution : @yossh

Time Complexity : O(N+K)

PS: This approach is similar to "Next Greater Element" problem in LC.