




from collections import deque



def      UpperCAmelCase_   (     __UpperCamelCase     ):
    return input(__UpperCamelCase     ).strip().split(""" """     )



def      UpperCAmelCase_   (     __UpperCamelCase,    __UpperCamelCase     ):
    SCREAMING_SNAKE_CASE__       ={}
    for i in range(__UpperCamelCase     ):
        SCREAMING_SNAKE_CASE__       =[]

    for e in range(__UpperCamelCase     ):
        SCREAMING_SNAKE_CASE__      ,		SCREAMING_SNAKE_CASE__       =(int(__UpperCamelCase     ) for i in _input(f"""Edge {e + 1}: <node1> <node2> """     ))
        graph[x].append(__UpperCamelCase     )
    return graph



def      UpperCAmelCase_   (     __UpperCamelCase,    __UpperCamelCase     ):
    SCREAMING_SNAKE_CASE__       ={}
    for i in range(__UpperCamelCase     ):
        SCREAMING_SNAKE_CASE__       =[]

    for e in range(__UpperCamelCase     ):
        SCREAMING_SNAKE_CASE__      ,		SCREAMING_SNAKE_CASE__       =(int(__UpperCamelCase     ) for i in _input(f"""Edge {e + 1}: <node1> <node2> """     ))
        graph[x].append(__UpperCamelCase     )
        graph[y].append(__UpperCamelCase     )
    return graph



def      UpperCAmelCase_   (     __UpperCamelCase,    __UpperCamelCase     ):
    SCREAMING_SNAKE_CASE__       ={}
    for i in range(__UpperCamelCase     ):
        SCREAMING_SNAKE_CASE__       =[]

    for e in range(__UpperCamelCase     ):
        SCREAMING_SNAKE_CASE__      ,		SCREAMING_SNAKE_CASE__      ,		SCREAMING_SNAKE_CASE__       =(int(__UpperCamelCase     ) for i in _input(f"""Edge {e + 1}: <node1> <node2> <weight> """     ))
        graph[x].append((y, w)     )
        graph[y].append((x, w)     )
    return graph


if __name__ == "__main__":
    lowerCamelCase_						, lowerCamelCase_  						=       (int(i) for i in _input("Number of nodes and edges: "))

    lowerCamelCase_  						=       int(
        _input(
            "Press 1 or 2 or 3 \n"
            "1. Unweighted directed \n"
            "2. Unweighted undirected \n"
            "3. Weighted undirected \n"
        )[0]
    )

    lowerCamelCase_  						=       {
        1: initialize_unweighted_directed_graph,
        2: initialize_unweighted_undirected_graph,
        3: initialize_weighted_undirected_graph,
    }[graph_choice](n, m)



def      UpperCAmelCase_   (     __UpperCamelCase,    __UpperCamelCase     ):
    SCREAMING_SNAKE_CASE__      ,		SCREAMING_SNAKE_CASE__       ={s}, [s]
    print(__UpperCamelCase     )
    while _s:
        SCREAMING_SNAKE_CASE__       =0
        for i in g[_s[-1]]:
            if i not in vis:
                _s.append(__UpperCamelCase     )
                vis.add(__UpperCamelCase     )
                SCREAMING_SNAKE_CASE__       =1
                print(__UpperCamelCase     )
                break
        if not flag:
            _s.pop()



def      UpperCAmelCase_   (     __UpperCamelCase,    __UpperCamelCase     ):
    SCREAMING_SNAKE_CASE__      ,		SCREAMING_SNAKE_CASE__       ={s}, deque([s]     )
    print(__UpperCamelCase     )
    while q:
        SCREAMING_SNAKE_CASE__       =q.popleft()
        for v in g[u]:
            if v not in vis:
                vis.add(__UpperCamelCase     )
                q.append(__UpperCamelCase     )
                print(__UpperCamelCase     )



def      UpperCAmelCase_   (     __UpperCamelCase,    __UpperCamelCase     ):
    SCREAMING_SNAKE_CASE__      ,		SCREAMING_SNAKE_CASE__      ,		SCREAMING_SNAKE_CASE__       ={s: 0}, set(), {s: 0}
    while True:
        if len(__UpperCamelCase     ) == len(__UpperCamelCase     ) - 1:
            break
        SCREAMING_SNAKE_CASE__       =100_000
        for i in dist:
            if i not in known and dist[i] < mini:
                SCREAMING_SNAKE_CASE__       =dist[i]
                SCREAMING_SNAKE_CASE__       =i
        known.add(__UpperCamelCase     )
        for v in g[u]:
            if v[0] not in known and dist[u] + v[1] < dist.get(v[0],    100_000     ):
                SCREAMING_SNAKE_CASE__       =dist[u] + v[1]
                SCREAMING_SNAKE_CASE__       =u
    for i in dist:
        if i != s:
            print(dist[i]     )



def      UpperCAmelCase_   (     __UpperCamelCase,    __UpperCamelCase=None,    __UpperCamelCase=None     ):
    if q is None:
        SCREAMING_SNAKE_CASE__       =[1]
    if ind is None:
        SCREAMING_SNAKE_CASE__       =[0] * (len(__UpperCamelCase     ) + 1)  # SInce oth Index is ignored
        for u in g:
            for v in g[u]:
                ind[v] += 1
        SCREAMING_SNAKE_CASE__       =deque()
        for i in g:
            if ind[i] == 0:
                q.append(__UpperCamelCase     )
    if len(__UpperCamelCase     ) == 0:
        return
    SCREAMING_SNAKE_CASE__       =q.popleft()
    print(__UpperCamelCase     )
    for w in g[v]:
        ind[w] -= 1
        if ind[w] == 0:
            q.append(__UpperCamelCase     )
    topo(__UpperCamelCase,    __UpperCamelCase,    __UpperCamelCase     )



def      UpperCAmelCase_   (     ):
    SCREAMING_SNAKE_CASE__       =input().strip()
    SCREAMING_SNAKE_CASE__       =[]
    for _ in range(__UpperCamelCase     ):
        a.append(map(__UpperCamelCase,    input().strip().split()     )     )
    return a, n



def      UpperCAmelCase_   (     __UpperCamelCase     ):
    ((SCREAMING_SNAKE_CASE__)      ,		(SCREAMING_SNAKE_CASE__))       =a_and_n
    SCREAMING_SNAKE_CASE__       =list(__UpperCamelCase     )
    SCREAMING_SNAKE_CASE__       =[[0] * n for i in range(__UpperCamelCase     )]
    for k in range(__UpperCamelCase     ):
        for i in range(__UpperCamelCase     ):
            for j in range(__UpperCamelCase     ):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    SCREAMING_SNAKE_CASE__       =dist[i][k] + dist[k][j]
                    SCREAMING_SNAKE_CASE__       =k
    print(__UpperCamelCase     )



def      UpperCAmelCase_   (     __UpperCamelCase,    __UpperCamelCase     ):
    SCREAMING_SNAKE_CASE__      ,		SCREAMING_SNAKE_CASE__      ,		SCREAMING_SNAKE_CASE__       ={s: 0}, set(), {s: 0}
    while True:
        if len(__UpperCamelCase     ) == len(__UpperCamelCase     ) - 1:
            break
        SCREAMING_SNAKE_CASE__       =100_000
        for i in dist:
            if i not in known and dist[i] < mini:
                SCREAMING_SNAKE_CASE__       =dist[i]
                SCREAMING_SNAKE_CASE__       =i
        known.add(__UpperCamelCase     )
        for v in g[u]:
            if v[0] not in known and v[1] < dist.get(v[0],    100_000     ):
                SCREAMING_SNAKE_CASE__       =v[1]
                SCREAMING_SNAKE_CASE__       =u
    return dist



def      UpperCAmelCase_   (     ):
    SCREAMING_SNAKE_CASE__      ,		SCREAMING_SNAKE_CASE__       =map(__UpperCamelCase,    input().split(""" """     )     )
    SCREAMING_SNAKE_CASE__       =[]
    for _ in range(__UpperCamelCase     ):
        edges.append(map(__UpperCamelCase,    input().split(""" """     )     )     )
    return edges, n



def      UpperCAmelCase_   (     __UpperCamelCase     ):
    # Sort edges on the basis of distance
    ((SCREAMING_SNAKE_CASE__)      ,		(SCREAMING_SNAKE_CASE__))       =e_and_n
    e.sort(reverse=__UpperCamelCase,    key=lambda __UpperCamelCase     : x[2]     )
    SCREAMING_SNAKE_CASE__       =[{i} for i in range(1,    n + 1     )]
    while True:
        if len(__UpperCamelCase     ) == 1:
            break
        print(__UpperCamelCase     )
        SCREAMING_SNAKE_CASE__       =e.pop()
        for i in range(len(__UpperCamelCase     )     ):
            if x[0] in s[i]:
                break
        for j in range(len(__UpperCamelCase     )     ):
            if x[1] in s[j]:
                if i == j:
                    break
                s[j].update(s[i]     )
                s.pop(__UpperCamelCase     )
                break




def      UpperCAmelCase_   (     __UpperCamelCase     ):
    SCREAMING_SNAKE_CASE__       =[]
    for node in graph:
        if not graph[node]:
            isolated.append(__UpperCamelCase     )
    return isolated












def      UpperCAmelCase_   (     __UpperCamelCase,    __UpperCamelCase     ):
    SCREAMING_SNAKE_CASE__       =len(__UpperCamelCase     )
    # Create a stack and push index of fist element to it
    SCREAMING_SNAKE_CASE__       =[]
    st.append(0     )

    # Span value of first element is always 1
    SCREAMING_SNAKE_CASE__       =1

    # Calculate span values for rest of the elements
    for i in range(1,    __UpperCamelCase     ):
        # Pop elements from stack while stack is not
        # empty and top of stack is smaller than price[i]
        while len(__UpperCamelCase     ) > 0 and price[st[0]] <= price[i]:
            st.pop()

        # If stack becomes empty, then price[i] is greater
        # than all elements on left of it, i.e. price[0],
        # price[1], ..price[i-1]. Else the price[i]  is
        # greater than elements after top of stack
        SCREAMING_SNAKE_CASE__       =i + 1 if len(__UpperCamelCase     ) <= 0 else (i - st[0])

        # Push this element to stack
        st.append(__UpperCamelCase     )



def      UpperCAmelCase_   (     __UpperCamelCase,    __UpperCamelCase     ):
    for i in range(0,    __UpperCamelCase     ):
        print(arr[i],    end=""" """     )


# Driver program to test above function
lowerCamelCase_  						=       [10, 4, 5, 90, 120, 80]
lowerCamelCase_  						=       [0 for i in range(len(price) + 1)]

# Fill the span values in array S[]
calculation_span(price, S)




print_array(S, len(price))






