I NEED AN NLOGN OR LINEAR SOLUTION TO THIS PROBLEM!

I NEED A FASTER SOLUTION THAN THE ONE GIVEN BELOW!! The solutionbelow runs in quadratic time, I need one faster than this.

I REPEAT I NEED A FASTER SOLUTION!! THE SOLUTION GIVEN BELOW ISTOO SLOW!

Slow Solution:

def predictAnswer(stockData, queries):  stockData = [0] + stockData  length = len(stockData)  ans = []  for q in queries:    l = q-1    r = q+1    flag = True    while l > 0 or r < length:      if l > 0 and stockData[l] < stockData[q]:        ans.append(l)        flag = False        break      if r < length and stockData[r] < stockData[q]:        ans.append(r)        flag = False        break      l -= 1      r += 1    if flag:      ans.append(-1)  return ans

Question:

The function predictAnswer should be made based on thefollowing.

In the prediction game, the first player gives the second playersome stock market data for some consecutive days. The data containsa company's stock price on each day. The rules for the gameare:

1. Player 1 will tell player 2 a day number
2. Player 2 has to find the nearest day on which stock price issmaller than the given day
3. If there are two results, then player 2 finds the day numberwhich is smaller
4. If no such day exits, then the answer is -1.

Example 1;

stockData size n =10;

stockData = [5,6,8,4,9,10,8,3,6,4]

queries = [6,5,4]

Result is [5,4,8]

On day 6, the stock price is 10. Both 9 and 8 are lower pricesone day away. Choose 9 (day 5) because it is before day 6. On day5, the stock price is 9. 4 is the closest lower price on day 4. Onday 4, the stock price is 4. The only lower price is on day 8. Thereturn array is [5,4,8]

Example - 2

stockData size n = 10

stockData = [5,6,8,4,9,10,8,3,6,4]

queries = [3,1,8]

Result is [2,4,-1]

If the day number is 3.both days 2 and 4 are smaller.choose theearlier day,day 2.

If the day number is 1,day 4 is the closet day with a smallerprice.

If the day number is 8,there is no day where the price is lessthan 3.

The return array is [2,4,-1]

/*

     * Complete the 'predictAnswer'function below.

     *

     * The function is expected toreturn an INTEGER_ARRAY.

     * The function accepts followingparameters:

     *  1. INTEGER_ARRAYstockData

     *  2. INTEGER_ARRAYqueries

     */

def predictAnswer(stockData, queries):