Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.
The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.
For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].
 

Example 1:
Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]
Explanation: 
First, S = StockSpanner() is initialized.  Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.

 
Note:

Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
There will be at most 10000 calls to StockSpanner.next per test case.
There will be at most 150000 calls to StockSpanner.next across all test cases.
The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.

Difficulty: interview

Starter code:

class StockSpanner:
    def __init__(self):
    def next(self, price: int) -> int:
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

Solutions:
class StockSpanner:

    def __init__(self):
        self.s=[]
        

    def next(self, price: int) -> int:
        stk=self.s
        curr_span=1
        
        while stk and stk[-1][0]<=price: #curr_price is > stack[-1][0]
            prev_price,prev_span=stk.pop()
            curr_span+=prev_span
        stk.append((price,curr_span))
        return curr_span
            
            
        
            
        
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.s = list()
        

    def next(self, price: int) -> int:
        weight = 1 
        stack = self.s
        while(stack and stack[-1][0] <= price):
            weight += stack[-1][-1] 
            stack.pop()
        stack.append((price, weight))
        return weight 


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
        self.span = []

    def next(self, price: int) -> int:
        res = 1
        if not self.stack or price < self.stack[-1]:
            self.stack.append(price)
            self.span.append(1)
        else:
            while self.stack and price >= self.stack[-1]:
                self.stack.pop()
                res += self.span.pop()
            self.stack.append(price)
            self.span.append(res)
        return res

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.st = []
        
    def next(self, price: int) -> int:
        cnt = 1
        while self.st and price >= self.st[-1][0]:
            cnt += self.st.pop()[1]
        self.st.append((price, cnt))
        print((self.st))
        return cnt
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stocks = []
        self.spans = []

    def next(self, price: int) -> int:
        self.stocks.append(price)
        self.spans.append(1)
        if len(self.stocks) == 1:
            return self.spans[0]
        idx = len(self.stocks) - 2
        cur_span = self.spans[-1]
        while(idx >= 0):
            if price < self.stocks[idx]:
                break
            else:
                cur_span += self.spans[idx]
                idx -= self.spans[idx]
        self.spans[-1] = cur_span
        return self.spans[-1]
                
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


'''
[100, 80, 60, 70, 60, 75, 85]
[1,    1,  1,  2,  1,  4,  6]
Assume that the span always has to include the current day.

Keep a stack of where spans start from left to right.
On a new price, pop elems from stack until the top is bigger than the current elem.
Then the top elem is the elem that ends the current day's span.



'''

class StockSpanner:

    def __init__(self):
        self.stack = list()
        self.ix = -1

    def next(self, price: int) -> int:
        self.ix += 1
        if not self.stack:
            self.stack.append((price, self.ix))
            return 1
        else:
            while self.stack and self.stack[-1][0] <= price:
                self.stack.pop()
            span_start = self.stack[-1][1] if self.stack else -1
            self.stack.append((price, self.ix))
            return self.ix - span_start


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:
    # Description
    # - Collect daily price quotes for some stock
    # - Return the span of that stock's price for the 
    #   current day
    #   - max number of consecutive days (starting from
    #     today and going backwards) for which the price of
    #     the stock was less than or equal to today's price
    # [1,2,3,3,3,4] => span = [1,2,3,4,5,6]
    # 
    # conditions
    # - Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5
    # - calls <= 10000 to StockSpanner.next per test
    # - calls <= 150000 to StockSpanner.next across all test cases
    #
    # Approach

    def __init__(self):
        self.history = []
        self.output = []

    def next(self, price: int) -> int:
        less_than_count = 1
        while self.history and self.history[-1][0] <= price:
            less_than_count += self.history.pop()[1]
        self.output.append(less_than_count)
        self.history.append((price, less_than_count))
        return self.output[-1]


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = [[float('inf'),-1]]
        self.idx = 0
        

    def next(self, price: int) -> int:
        while self.stack and self.stack[-1][0] <= price:
            self.stack.pop()
        ans = self.idx-self.stack[-1][1]
        self.stack.append([price, self.idx])
        self.idx += 1
        return ans


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        
        count = 1
        
        while self.stack and price >= self.stack[-1][0]:
            count += self.stack[-1][1]
            del self.stack[-1]
            
        self.stack.append([price, count])
        
        return self.stack[-1][1]

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
        self.idx = 0
        self.stack.append((float(\"inf\"),0))
        

    def next(self, price: int) -> int:
        self.idx += 1
        while(self.stack and self.stack[-1][0] <= price):
            self.stack.pop()
        self.stack.append((price,self.idx))
        if(self.idx == 1):
            return 1
        else:
            return self.stack[-1][1] - self.stack[-2][1]


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

class StockSpanner:

    def __init__(self):
        self.q = []
        

    def next(self, price: int) -> int:
        if not self.q or self.q[-1][0]>price:
            self.q.append((price,1))
            return 1
        elif self.q and self.q[-1][0] == price:
            c,l = self.q.pop()
            self.q.append((price,l+1))
            return l+1
        elif self.q:
            level=1
            while(self.q and self.q[-1][0]<=price):
                c,l = self.q.pop()
                level+=l
            self.q.append((price,level))
            return level
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.spanStk = []

    def next(self, price: int) -> int:
        if len(self.spanStk) == 0:
            self.spanStk.append((price, 1))
        else:
            new_weight = 1
            while len(self.spanStk) != 0 and self.spanStk[-1][0] <= price:
                new_weight += self.spanStk[-1][1]
                self.spanStk.pop()
            self.spanStk.append((price, new_weight))
        return self.spanStk[-1][1]
                


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:
    '''
        [100, 80, 60, 70, 60, 75, 85]
        
        [100] -> (100, 0, 0)
        [100, 80] -> (100, 0, 0), (80, 1, 1)
        [100, 80, 60] -> (100, 0, 0), (80, 1, 1), (60, 2, 2)
        [100, 80, 60, 70] -> (100, 0, 0), (80, 1, 1), (70, 2, 3)
        [100, 80, 60, 70, 60] -> (100, 0, 0), (80, 1, 1), (70, 2, 3), (60, 4, 4)
        [100, 80, 60, 70, 60, 75] -> (100, 0, 0), (80, 1, 1), (75, 2, 5)
        [100, 80, 60, 70, 60, 75, 85] -> (100, 0, 0), (85, 1, 6)                
    '''

    def __init__(self):
        self.stack = list()
        self.date = 0
        
        
    def next(self, price: int) -> int:
        if self.date == 0:
            self.date  += 1
            self.stack.append([price, 0])
            return 1
        else:            
            s, e = self.date, self.date
            while len(self.stack) > 0 and self.stack[-1][0] <= price:
                s = self.stack[-1][1]
                self.stack.pop()
            self.stack.append([price, s])
            self.date += 1
            return (e - s + 1)
                
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.arr = []

    def next(self, price: int) -> int:
        if len(self.arr) == 0:
            self.arr.append([price, 1])
            return 1
        
        i = len(self.arr) - 1
        count = 1
        while i >= 0 and price >= self.arr[i][0]:
            count += self.arr[i][1]
            i -= self.arr[i][1]
        
        self.arr.append([price, count])
        return count


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self._data = []

    def next(self, price: int) -> int:
        span = 1
        while self._data and self._data[-1][0] <= price:
            span += self._data.pop()[1]

        self._data.append((price, span))
        return span
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:
    '''
        [100, 80, 60, 70, 60, 75, 85]
        
        [100] -> (100, 0, 0)
        [100, 80] -> (100, 0, 0), (80, 1, 1)
        [100, 80, 60] -> (100, 0, 0), (80, 1, 1), (60, 2, 2)
        [100, 80, 60, 70] -> (100, 0, 0), (80, 1, 1), (70, 2, 3)
        [100, 80, 60, 70, 60] -> (100, 0, 0), (80, 1, 1), (70, 2, 3), (60, 4, 4)
        [100, 80, 60, 70, 60, 75] -> (100, 0, 0), (80, 1, 1), (75, 2, 5)
        [100, 80, 60, 70, 60, 75, 85] -> (100, 0, 0), (85, 1, 6)                
    '''

    def __init__(self):
        self.stack = list()
        self.date = 0
        
        
    def next(self, price: int) -> int:      
        s, e = self.date, self.date
        while len(self.stack) > 0 and self.stack[-1][0] <= price:
            s = self.stack[-1][1]
            self.stack.pop()
        self.stack.append([price, s])
        self.date += 1
        return (e - s + 1)
                
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.cur = -1
        self.stack = []
        self.prices = {}#[]
        

    def next(self, price: int) -> int:
        self.cur += 1
        # self.prices.append(price)
        self.prices[self.cur] = price
        while self.stack and self.prices[self.stack[-1]]<=price:
            self.prices.pop(self.stack.pop())
        
        res = self.cur-self.stack[-1] if self.stack else self.cur+1
        self.stack.append(self.cur)
        return res


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = [[0,1]]   
    def next(self, price: int) -> int:
        if price < self.stack[-1][0]:
            self.stack.append([price,1])
            return 1
        else:
            days = 0
            while self.stack and price >= self.stack[-1][0]:
                p, d = self.stack.pop()
                days += d # stack previous days
            try:
                days +=self.stack[-1][1] 
                self.stack[-1][1] = days # insert
            except:
                self.stack.append([0,days])
            self.stack.append([price,1])
        return days
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.idx = 0
        self.q = []

    def next(self, price: int) -> int:
        self.idx += 1
        if len(self.q) == 0 or self.q[-1][1] > price:
            self.q.append([self.idx, price])
            return 1
        else:
            while len(self.q) > 0 and self.q[-1][1] <= price:
                self.q.pop()
            if len(self.q) == 0:
                self.q.append([self.idx, price])
                return self.idx
            else:
                self.q.append([self.idx, price])
                return self.idx - self.q[-2][0]

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
        self.pre_less = []
        self.i = 0

    def next(self, price: int) -> int:
        self.i += 1
        while self.stack and self.stack[-1][1] <= price:
            self.stack.pop()
        
        result = None
        if not self.stack:
            result = self.i
        else:
            result = self.i - self.stack[-1][0]
        self.stack.append((self.i, price))
        return result


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        self.stack.append([price, 1])
        
        while len(self.stack) > 1 and self.stack[-1][0] >= self.stack[-2][0]:
            self.stack[-2][0] = self.stack[-1][0]
            self.stack[-2][1] += self.stack[-1][1]
            del self.stack[-1]
        return self.stack[-1][1]

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.idx = 0
        self.q = []

    def next(self, price: int) -> int:
        self.idx += 1
        if len(self.q) == 0 or self.q[-1][1] > price:
            self.q.append([self.idx, price])
            return 1
        else:
            while len(self.q) > 0 and self.q[-1][1] <= price:
                self.q.pop()
            if len(self.q) == 0:
                self.q.append([self.idx, price])
                return self.idx
            else:
                self.q.append([self.idx, price])
                return self.idx - self.q[-2][0]

        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:
    '''
        [100, 80, 60, 70, 60, 75, 85]
        
        [100] -> (100, 0, 0)
        [100, 80] -> (100, 0, 0), (80, 1, 1)
        [100, 80, 60] -> (100, 0, 0), (80, 1, 1), (60, 2, 2)
        [100, 80, 60, 70] -> (100, 0, 0), (80, 1, 1), (70, 2, 3)
        [100, 80, 60, 70, 60] -> (100, 0, 0), (80, 1, 1), (70, 2, 3), (60, 4, 4)
        [100, 80, 60, 70, 60, 75] -> (100, 0, 0), (80, 1, 1), (75, 2, 5)
        [100, 80, 60, 70, 60, 75, 85] -> (100, 0, 0), (85, 1, 6)                
    '''

    def __init__(self):
        self.stack = list()
        self.date = 0
        
        
    def next(self, price: int) -> int:
        if self.date == 0:
            self.date  += 1
            self.stack.append([price, 0, 0])
            return 1
        else:            
            s, e = self.date, self.date
            while len(self.stack) > 0 and self.stack[-1][0] <= price:
                s = self.stack[-1][1]
                self.stack.pop()
            self.stack.append([price, s, e])
            self.date += 1
            return (e - s + 1)
                
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:


    def __init__(self):
        
        self.stack = []
        self.ind = 0
        self.vals = []

    def next(self, price):

        #print(price, self.stack, self.ind, self.vals)
        
        self.vals+=[price]
        
        while len(self.stack)>0 and self.vals[self.stack[-1]]<=price:
            self.stack.pop()

        if len(self.stack)>0:
            res = self.ind - self.stack[-1]
        else:
            res = self.ind+1

        self.stack+=[self.ind]

        self.ind+=1
        
        #print(\"at end \", price, self.stack, self.ind, self.vals)

        if self.ind==1:
            return 1

        return res


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.dp = []
        self.price = []
    def next(self, price: int) -> int:
        if len(self.price)==0 or price<self.price[-1] : 
            self.dp.append(1)        
        else :
            i = len(self.price)-1
            tmp = 1
            while price>=self.price[i] and i>=0 :
                tmp += self.dp[i]
                i -= self.dp[i]
                
            self.dp.append(tmp)
                
        self.price.append(price)
        return self.dp[-1]


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.monotone_stack = []
        

    def next(self, price: int) -> int:
        stack = self.monotone_stack
        current_price, current_span = price, 1
        while stack and stack[-1][0]<=current_price:
            pre_price, pre_span = stack.pop()
            current_span+=pre_span
        stack.append((current_price, current_span))
        
        return current_span


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.st = []
        
    def next(self, price):
        span = 1
        while (len(self.st)>0) and self.st[-1][0] <= price:
            span = span + self.st[-1][1]
            self.st.pop()
        self.st.append((price,span))
        return span


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:
    # start from back
    # from collections import deque
    # queue=deque()
    
    def __init__(self):
        # self.queue=deque()
        self.stack=[]
    # if for the prev number is less than price we can just add one to its span, if its preceding bigger price is bigger than curr price
    def next(self, price: int) -> int:
        # span=1
        # stoppage_price=-1
        # for p,stop_price,s in self.queue:
        #     if p<=price and stop_price>price:
        #         span=s+span
        #         break
        #     elif p<=price and stop_price<=price:
        #         span+=1
        #     else:
        #         stoppage_price=p
        #         break
        # self.queue.appendleft((price,stoppage_price,span))
        # return span
        #add to stack
        # same as above sol but pop off same elements so the worst case is avoided
        res = 1
        while self.stack and self.stack[-1][0] <= price:
            res += self.stack.pop()[1]
        self.stack.append([price, res])
        return res
        
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:
    def __init__(self):
        self.stack = []
        self.uid = 1
        
    def next(self, price):
        while self.stack and self.stack[-1][0] <= price:
            self.stack.pop()
        if self.stack:
            res = self.uid - self.stack[-1][1]
        else:
            res = self.uid
        self.stack.append([price, self.uid])
        self.uid += 1
        return res       

class StockSpanner:
    def __init__(self):
        self.stack = []

    def next(self, price):
        res = 1
        while self.stack and self.stack[-1][0] <= price:
            res += self.stack.pop()[1]
        self.stack.append([price, res])
        return res

from collections import OrderedDict
class StockSpanner(OrderedDict):

    def __init__(self):
        self.counts = 0
        
    def next(self, price: int) -> int:
        i = len(self) - 1
        idx = self.counts
        items = list(self.items())
        while i >= 0 and items[i][0] <= price:
            idx = self[items[i][0]]
            self.popitem(last = True)
            i -= 1
        self[price] = idx
        self.counts += 1
        return self.counts - idx
        
            


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        res = 1
        while self.stack and price >= self.stack[-1][1]:
            res += self.stack.pop()[0]
            
        self.stack.append((res, price))
        
        return res

class StockSpanner:

    def __init__(self):
        self.stack = []
        self.i = 0

    def next(self, price: int) -> int:
        while self.stack and self.stack[-1][1] <= price:
            self.stack.pop()
        index = self.stack[-1][0] if self.stack else -1
        diff = self.i - index
        self.stack.append((self.i, price))
        self.i += 1
        return diff

class StockSpanner:

    def __init__(self):
        
        self.stack = []
     
      
    def next(self, price: int) -> int:
        
        cnt = 1
        while self.stack and self.stack[-1][0] <= price:
            
            p, c = self.stack.pop()
            cnt += c
        self.stack.append([price, cnt])
        
        return cnt
            
            



class StockSpanner:

    def __init__(self):
        self.prices = []
        self.spans = []
        
    def next(self, price: int) -> int:
        self.prices.append(price)
        value = 1
        index = len(self.spans)-1
        while(index>=0):
            if self.prices[index]<=price:
                value +=self.spans[index]
                index -=self.spans[index]
            else:
                break
        self.spans.append(value)
        return value
        
        
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        res = 1
        while self.stack and self.stack[-1][0] <= price:
            res += self.stack.pop()[1]
        self.stack.append([price, res])
        return res


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


import bisect
class StockSpanner:

    def __init__(self):
        self.stack = []
        
    def next(self, price: int) -> int:
        total = 1
        while self.stack and self.stack[-1][0] <= price:
            total += self.stack.pop()[1]
        self.stack.append((price, total))            
        return total

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.st = []

    def next(self, price: int) -> int:
        ans = 1
        while self.st and price >= self.st[-1][0]:
            ans += self.st.pop()[1]
        self.st.append([price, ans])
        return ans

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.day = 1
        self.ascendingStack = [(0, float(\"inf\"))]
    
    def next(self, price: int) -> int:
        while self.ascendingStack[-1][1] <= price:
            self.ascendingStack.pop()
            
        days = self.day - self.ascendingStack[-1][0]
        self.ascendingStack.append((self.day, price))
        self.day+=1
        
        return days

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        weight = 1
        while self.stack and self.stack[-1][0]<=price:
            weight += self.stack.pop()[1]
        
        self.stack.append([price, weight])
        return weight


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stock = [] # a list that stores tuples (date_stock_price, span_start_index)
    
    def next(self, price: int) -> int:
        if not self.stock or (price < self.stock[-1][0]):
            span = 1
            self.stock.append((price, len(self.stock)))
        else:
            i = self.stock[-1][1]-1
            while i >= 0 and self.stock[i][0] <= price:
                i -= 1
            span = len(self.stock) - i
            self.stock.append((price, i+1))
        return span


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.prices = []
        self.lastP = 0
        self.lastCount = 0
        
        

    def next(self, price: int) -> int:
        if len(self.prices) == 0:
            
            self.lastCount = 1
            self.lastP = 0
            self.prices.append(price)
            return 1
        count = self.lastCount
        #print(self.prices)
        if price == self.prices[-1]:
            count +=1
            self.lastCount = count
        elif price > self.prices[-1]:
            count+=1
            isB = False
            for i in range(self.lastP-1,-1,-1):
                if self.prices[i] <= price:
                    count+=1
                    self.lastP = i
                else:
                    isB = True
                    break
            if isB:
                self.lastP = i+1
            else:
                self.lastP = 0
            self.lastCount = count
        elif price < self.prices[-1]:
            count = 1
            self.lastCount = count
            self.lastP = len(self.prices)
        self.prices.append(price)
        return count

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
        

    def next(self, price: int) -> int:
        # stack, almost by myself. Idea is simple. Brute force - store prices in stack, and at every new price iterate all over stack. Innefficient!
        # But we could push to stack price and how much times we occured smaller values. For example, no need to store in stack [1,2,3,4,13], just store stack[13: 5] - and if next price would be greater than 13 - maybe 40 - we just pop 13,5 from stack and append 5 to result. Then push [40,6] to stack
        # monotonically decreasing stack?
        # good explanation here - https://leetcode.com/problems/online-stock-span/discuss/168311/C%2B%2BJavaPython-O(1)
        result = 1
        while self.stack and self.stack[-1][0] <= price:
            previous_calculated_result = self.stack.pop()[1]
            result += previous_calculated_result

        self.stack.append([price, result])
        print((self.stack))
        return result
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
        

    def next(self, price: int) -> int:
        # stack, almost by myself. Idea is simple. Brute force - store prices in stack, and at every new price iterate all over stack. Innefficient!
        # But we could push to stack price and how much times we occured smaller values. For example, no need to store in stack [1,2,3,4,13], just store stack[13: 5] - and if next price would be greater than 13 - maybe 40 - we just pop 13,5 from stack and append 5 to result. Then push [40,6] to stack
        # monotonically decreasing stack?
        result = 1
        while self.stack and self.stack[-1][0] <= price:
            previous_calculated_result = self.stack.pop()[1]
            result += previous_calculated_result

        self.stack.append([price, result])
        print((self.stack))
        return result
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
      
        

    def next(self, price):
        weight = 1
        print((self.stack))
        while self.stack and self.stack[-1][0] <= price:
            weight += self.stack.pop()[1]
        self.stack.append((price, weight))
        return weight
            
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        # from collections import defaultdict
        self.Dict = defaultdict(int)
        self.s = []
        self.count = 0
    def next(self, price: int) -> int:
        if len(self.s) == 0:
            self.s.append((self.count, price))
            self.Dict[(self.count, price)] += 1
            ans = self.Dict[(self.count, price)]
            self.count += 1
            return ans
        else:
            while len(self.s) != 0 and price >= self.s[-1][1]:
                self.Dict[(self.count, price)] += self.Dict[(self.s[-1][0], self.s[-1][1])] 
                self.s.pop(-1)
            self.s.append((self.count, price))
            self.Dict[(self.count, price)] += 1
            ans = self.Dict[(self.count, price)]
            self.count += 1
            return ans
            
                
        
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        weight = 1
        while self.stack and self.stack[-1][0]<=price:
            weight+=self.stack.pop()[1]
        self.stack.append((price, weight))
        return weight


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.prices = []
        self.counter = []
        

    def next(self, price: int) -> int:
        self.prices.append(price)
        length = len(self.prices)
        
        if length == 1:
            self.counter.append(1)
            
        else:
            if self.prices[-2] <= price:
                cnt = 0
                for i in range(length-self.counter[-1]-1, -1,-1):
                    if self.prices[i] <= price:
                        cnt += 1
                    else: 
                        break
                self.counter.append(self.counter[-1]+cnt)
            else:
                self.counter.append(1)
        return self.counter[-1]


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:
    \"\"\"
    Solution:
        1. use a stack to store the current max price, and the corresponding span
        2. comprare the comming price, and merge to the stack if needed
    Time complexity: O(n)
    Space complexity: O(n) if the span is always 1
    \"\"\"
    def __init__(self):
        self.stack = []
        

    def next(self, price: int) -> int:
        if not self.stack:
            self.stack.append([price, 1])
            return self.stack[-1][1]
        count = 1
        while self.stack and price >= self.stack[-1][0]:
            count += self.stack[-1][1]
            self.stack.pop()
        self.stack.append([price, count])
        
        return self.stack[-1][1]
            
        
            
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stocks = []
        self.spans = []

    def next(self, price: int) -> int:
        if not self.spans:
            self.spans.append(1)
            self.stocks.append(price)
            return 1
        elif price < self.stocks[-1]:
            self.spans.append(1)
            self.stocks.append(price)
            return 1
        else:
            newSpan = self.spans[-1]
            i = -1 * newSpan - 1
            while i >= -1 * len(self.stocks) and price >= self.stocks[i]:
                newSpan += 1
                i -= 1
            newSpan += 1
            self.spans.append(newSpan)
            self.stocks.append(price)
            return newSpan
            


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        count = 1
        while self.stack and self.stack[-1][0]<=price: count+=self.stack.pop()[1]
        self.stack.append([price,count])
        return count


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = [[0,1]]   
    def next(self, price: int) -> int:
        if  not self.stack:
            self.stack.append([price,1])
            return 1
        elif self.stack and price < self.stack[-1][0]:
            self.stack.append([price,1])
            return 1
        else:
            days = 0
            while self.stack and price >= self.stack[-1][0]:
                p, d = self.stack.pop()
                days += d # stack previous days
            try:
                days +=self.stack[-1][1] 
                self.stack[-1][1] = days # insert
            except:
                self.stack.append([0,days])
        
            self.stack.append([price,1])
            print((self.stack))
        return days
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack=[]
        

    def next(self, price: int) -> int:
        w=1
        while self.stack and self.stack[-1][0]<=price:
            w+=self.stack.pop()[1]
        self.stack.append([price,w])
        return w


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.monotone_stack = []
        

    def next(self, price: int) -> int:
        stack = self.monotone_stack
        cur_price_quote, cur_price_span = price , 1
        while stack and stack[-1][0] <= cur_price_quote:
            prev_price_quote, prev_price_span = stack.pop()
            cur_price_span += prev_price_span
        stack.append((cur_price_quote, cur_price_span))
        return cur_price_span






class StockSpanner:

    def __init__(self):
        self.stack = []
        
    def next(self, price: int) -> int:
        res = 1
        i = len(self.stack)
        while self.stack and self.stack[-1][0] <= price:
            (x,c) = self.stack.pop()
            res += c
        self.stack.append((price,res))
        return res
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
        self.num = 0
        self.stack.append((float('inf'), 0))

    def next(self, price: int) -> int:
        ret = 1
        self.num += 1
        while self.stack[-1][0] <= price:
            self.stack.pop()
        topIndex = self.stack[-1][1]
        self.stack.append((price, self.num))
        return self.num - topIndex


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        
        self.stack = []

    def next(self, price: int) -> int:
        
        days = 1
        
        while self.stack and self.stack[-1][0] <= price:
            days += self.stack.pop()[1]
        print((self.stack))
        self.stack.append((price,days))
        return days


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256


class StockSpanner:

    def __init__(self):
        self.s = []
        self.i = 0

    def next(self, price: int) -> int:
        s = self.s
        i = self.i

        while len(s) and s[-1][0] <= price:
            s.pop()

        ans = i + 1
        if len(s):
            ans = i - s[-1][1]
        s.append((price, i))
        self.i += 1
        return ans


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
\"\"\"
s = StockSpanner()

print(s.next(100))
print(s.next(80))
print(s.next(60))
print(s.next(70))
print(s.next(60))
print(s.next(75))
print(s.next(85))
\"\"\"


class StockSpanner:

    def __init__(self):
        self.priceList = []
        self.n=0
        self.prevSpan = 0
        self.curSpan = 0
    def next(self, price: int) -> int:
        if not self.priceList:
            self.priceList.append(price)
            self.n+=1
            self.curSpan = 1
            self.prevSpan = self.curSpan
            return self.curSpan
        prev = self.priceList[-1]
        self.priceList.append(price)
        self.n+=1
        if price<prev:
            self.curSpan = 1
            self.prevSpan = self.curSpan
            return self.curSpan
        else:
            self.curSpan = 1+self.prevSpan
            i = self.n-self.curSpan-1
            # if i >= 0:
            #     cur = priceList[i]
            while i>=0 and self.priceList[i]<=price:
                self.curSpan+=1
                i = self.n-self.curSpan-1
            self.prevSpan = self.curSpan
            return self.curSpan
                
        
        
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        
        c = 1
        while self.stack and self.stack[-1][0] <= price:
            c += self.stack.pop()[1]
            
        self.stack.append([price,c])
        return c
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


from collections import deque

class StockSpanner:

    def __init__(self):
        # self.running_count = 0
        self.stack = deque()
        

    def next(self, price: int) -> int:
        
        weight = 1
        
        while self.stack and self.stack[-1][0] <= price:
            weight += self.stack.pop()[1]
        
        self.stack.append((price, weight))
        
        return weight
        
        
        
        
        
        
        
        
#         self.running_count += 1

#         if not self.queue:
#             self.queue.append((price, self.running_count))
#             return self.running_count 
        
#         if price < self.queue[-1][0]:
#             self.queue.append((price, self.running_count))
#             return 1
        
#         else:
#             while self.queue and price >= self.queue[-1][0]:
#                 self.queue.pop()
            
#             if not self.queue:
#                 self.queue.append((price, self.running_count))
#                 return self.running_count
            
#             ans = self.running_count - self.queue[-1][1]                    
#             self.queue.append((price, self.running_count))
            
#             return ans
            
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner(object):
    def __init__(self):
        self.stack = []

    def next(self, price):
        weight = 1
        while self.stack and self.stack[-1][0] <= price:
            weight += self.stack.pop()[1]
        self.stack.append((price, weight))
        return weight

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        weight = 1
        while self.stack and self.stack[-1][0] <= price:
            weight += self.stack.pop()[1]
        self.stack.append((price, weight))
        return weight

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
        self.cnt = 0

    def next(self, price: int) -> int:
        # self.cnt += 1
        if not self.stack:
            self.stack.append((price, 1))
            return 1
        else:
            cnt_removed = 1
            while self.stack and self.stack[-1][0] <= price:
                cnt_removed += self.stack.pop()[1]
            self.stack.append((price, cnt_removed))
            return cnt_removed
            
            
            


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.nums = []
        self.larger_pos = []
        

    def next(self, price: int) -> int:
        if not self.nums:
            self.nums.append(price)
            self.larger_pos.append(-1)
            return 1
        num = self.nums[-1]
        pos = len(self.larger_pos) - 1
        while price >= num:
            pos = self.larger_pos[pos]
            if pos == -1:
                self.nums.append(price)
                self.larger_pos.append(-1)
                return len(self.nums)
            num = self.nums[pos]
        self.nums.append(price)
        self.larger_pos.append(pos)
        return len(self.nums) - 1 - pos


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        span = 1
        # while there is a stack and the top of the stack(aka the previous values) has a value that's less than or equal to the current price
        while self.stack and self.stack[-1][0] <= price: 
            span = span + self.stack.pop()[1]  # update the span
        self.stack.append([price, span])
    
        return span

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.st = []
        
    def next(self, price: int) -> int:
        cnt = 1
        while self.st and price >= self.st[-1][0]:
            cnt += self.st.pop()[1]
        self.st.append((price, cnt))
        return cnt
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.st = []

    def next(self, price: int) -> int:
        sp = 1
        while self.st and self.st[-1][0]<=price:
            sp += self.st.pop()[1]
        self.st.append([price,sp])
        return sp
        
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack=[]
        

    def next(self, price: int) -> int:
        count=1
        while self.stack and price>=self.stack[-1][0]:
            count+=self.stack.pop()[1]
        self.stack.append((price,count))
        return count
            
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class MyStack:
    def __init__(self):
        self.stack = []

    def push(self, data: int):
        self.stack.append(data)

    def pop(self) -> int:
        if self.isEmpty():
            return \"No element in the Stack\"
        else:
            return self.stack.pop()

    def top(self) -> int:
        if self.isEmpty():
            return (\"No element in the Stack\")
        else:
            return self.stack[-1]

    def isEmpty(self) -> bool:
        return len(self.stack) == 0

class StockSpanner:

    def __init__(self):
        self.maxStack = MyStack()
        self.nums = []
        self.index = -1

    def next(self, price: int) -> int:
        self.index += 1
        while not self.maxStack.isEmpty() and self.nums[self.maxStack.top()] <= price:
            self.maxStack.pop()
        if self.maxStack.isEmpty():
            p = -1
        else:
            p = self.maxStack.top()
        self.maxStack.push(self.index)
        self.nums.append(price)
        return self.index - p

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        res = 1
        while self.stack and self.stack[-1][0] <= price:
            res += self.stack.pop()[1]
        self.stack.append([price, res])
        return res
            
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stock = []

    def next(self, price: int) -> int:
        val = 1
        while self.stock and self.stock[-1][0] <= price:
            val += self.stock.pop()[1]
        
        self.stock.append((price, val))
        return val


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price):
        res = 1
        while self.stack and self.stack[-1][0] <= price:
            res += self.stack.pop()[1]
        self.stack.append([price, res])
        return res
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        weight = 1
        while self.stack and self.stack[-1][0] <= price:
            weight += self.stack.pop()[1]
        self.stack.append((price,weight))
        return weight
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        count = 1
        while self.stack and self.stack[-1][0] <= price:
            s, c = self.stack.pop()
            count += c
        self.stack.append((price, count))
        return count


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stacks = []

    def next(self, price: int) -> int:
        if len(self.stacks) == 0:
            self.stacks.append([price,1])
            return 1
        else:
            p = 1
            while( len(self.stacks) > 0 and  self.stacks[-1][0] <= price):
                ele = self.stacks.pop()
                p += ele[1]
            self.stacks.append([price,p])
            return p
            
                
            
        
        

        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        span = 1
        while self.stack and price >= self.stack[-1][0]:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
        self.cnt = 0

    def next(self, price: int) -> int:
        # self.cnt += 1
        if not self.stack:
            self.stack.append((price, 1))
            return 1
        else:
            cnt_removed = 1
            while self.stack and self.stack[-1][0] <= price:
                node = self.stack.pop()
                cnt_removed += node[1]
            self.stack.append((price, cnt_removed))
            if cnt_removed > 1:
                return cnt_removed
            else:
                return 1
            
            
            


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price):
        res = 1
        while self.stack and self.stack[-1][0] <= price:
            res += self.stack.pop()[1]
        self.stack.append([price, res])
        return res


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
        

    def next(self, price: int) -> int:
        weight = 1
        while self.stack and self.stack[-1][0] <= price:
            weight += self.stack.pop()[1]
        self.stack.append((price, weight))
        return weight
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
        
        

    def next(self, price: int) -> int:
        idx =1
        while self.stack and self.stack[-1][0]<= price:
            idx += self.stack.pop()[1]
        self.stack.append([price,idx])      
        return idx
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
        

    def next(self, price: int) -> int:
        weight = 1
        while self.stack != [] and price >= self.stack[-1][0]:
            weight += self.stack.pop()[1]
        self.stack.append((price, weight))
        return weight


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stocks = []
        self.topStocks = []

    def next(self, price: int) -> int:
        
        while(len(self.topStocks)>0 and self.stocks[self.topStocks[-1]] <= price):
            self.topStocks.pop()
        flag = self.topStocks[-1] if len(self.topStocks)>0 else -1
        self.topStocks.append(len(self.stocks))
        self.stocks.append(price)
        return len(self.stocks) - flag-1
            


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack=[]
        self.len=-2
        

    def next(self, price: int) -> int:
        if not self.stack:
            self.stack.append([price,1])
            return 1
        
        ans=0
        while(self.stack and self.stack[-1][0]<=price):
            elm=self.stack.pop()
            ans+=elm[1]
        self.stack.append([price,ans+1])
        return ans+1
                
            
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)



'''
curr=0
[[inf,0]]

'''
from collections import deque
class StockSpanner:

    def __init__(self):
        self.stack=deque()
        self.counter=0
        self.stack.append([float('inf'),0])
    
    def update_stack(self,value):
        while(value>=self.stack[len(self.stack)-1][0]):
            self.stack.pop()

    def next(self, price: int) -> int:
        self.counter+=1
        self.update_stack(price)
        diff=abs(self.counter-self.stack[len(self.stack)-1][1])
        self.stack.append([price,self.counter])
        return diff


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.st = []
        self.idx = 0
        

    def next(self, price: int) -> int:
        while len(self.st) and self.st[-1][0] <= price:
            self.st.pop()
        ans = self.idx - (0 if not len(self.st) else self.st[-1][1])+1
        self.st.append((price, self.idx+1))
        self.idx += 1
        return ans
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.prices = []
        # left[i]: index of first price on the left > prices[i]
        self.left = []

    def next(self, price: int) -> int:
        cur = len(self.prices) - 1
        while cur >= 0 and self.prices[cur] <= price:
            cur = self.left[cur]
        
        self.left.append(cur)
        self.prices.append(price)
        return len(self.prices) - 1 - cur


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.prices = []
        self.decreasing_stack = []

    def next(self, price: int) -> int:
        while self.decreasing_stack and self.prices[self.decreasing_stack[-1]]<=price:
            self.decreasing_stack.pop()
        ret = len(self.prices)-self.decreasing_stack[-1] if self.decreasing_stack else len(self.prices)+1
        self.decreasing_stack.append(len(self.prices))
        self.prices.append(price)
        return ret
        

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.s=[]
        self.O=[]
        

    def next(self, price: int) -> int:
        self.s.append(price)
        o = 0
        if len(self.s)==1:
            self.O.append(1)
            return 1
        l = len(self.s)
        i = l-2
        o =1
        # print(self.O,self.s,i)
        while i>=0:
            # print(self.s[i])
            if self.s[i]<=price:
                o+=self.O[i]
                i-=self.O[i]
            else:
                break
        self.O.append(o)
        return o


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []
        self.indx = -1
        self.results = []

    def next(self, price: int) -> int:
        self.indx += 1
        while len(self.stack) > 0 and self.stack[-1][1] <= price:
            self.stack.pop()
        if len(self.stack) == 0:
            self.stack.append([self.indx, price])
            return self.indx + 1
        result = self.stack[-1][0]
        self.stack.append([self.indx, price])
        
        return self.indx - result
            
            
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        weight = 1
        while self.stack and self.stack[-1][0] <= price:
            _, currentWeight = self.stack.pop()
            weight += currentWeight
        self.stack.append((price, weight))
        return weight
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)


class StockSpanner:

    def __init__(self):
        self.s = [float('inf')]
        self.pos = [0]
        self.num = 1
        

    def next(self, price: int) -> int:
        while self.s and self.s[-1] <= price:
            self.s.pop()
            self.pos.pop()
        r = self.num - self.pos[-1]
        self.s.append(price)
        self.pos.append(self.num)
        self.num += 1
        return r
        


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)