Editing 3705 - rectangles (section)

== Rezolvare == 
<syntaxhighlight lang="python3" line="1">
MaxN = 1000010
mod = 10**9 + 7

v = [0] * MaxN
left1 = [0] * MaxN
left2 = [0] * MaxN
right1 = [0] * MaxN
right2 = [0] * MaxN

def multiply(a, b, c, d):
    return ((a * b) % mod) * ((c * d) % mod) % mod

def citeste_si_verifica_elemente(n):
    print(f"Introduceți {n} elemente (fiecare urmat de Enter):")
    v_temp = []
    for i in range(1, n + 1):
        try:
            x = int(input(f"Elementul {i}: "))
            if not (1 <= x <= 10**9):
                print("Datele nu corespund restricțiilor impuse")
                return None
            v_temp.append(x)
        except ValueError:
            print("Datele nu corespund restricțiilor impuse")
            return None
    return v_temp

def main():
    try:
        n = int(input("Introduceți lungimea șirului: "))
        if not (1 <= n <= 10**6):
            print("Datele nu corespund restricțiilor impuse")
            return
    except ValueError:
        print("Datele nu corespund restricțiilor impuse")
        return
    
    v_input = citeste_si_verifica_elemente(n)
    if v_input is None:
        return
    
    v[1:n+1] = v_input

    for i in range(1, n+1):
        left1[i] = left2[i] = 0
        right1[i] = right2[i] = n + 1
    
    st1, st2, aux = [], [], []
    for i in range(1, n+1):
        while st2 and v[i] > v[st2[-1]]:
            right2[st2[-1]] = i
            st2.pop()
        while st1 and v[i] > v[st1[-1]]:
            right1[st1[-1]] = i
            aux.append(st1.pop())
        st1.append(i)
        while aux:
            st2.append(aux.pop())
    
    st1.clear()
    st2.clear()
    
    for i in range(n, 0, -1):
        while st2 and v[i] >= v[st2[-1]]:
            left2[st2[-1]] = i
            st2.pop()
        while st1 and v[i] >= v[st1[-1]]:
            left1[st1[-1]] = i
            aux.append(st1.pop())
        st1.append(i)
        while aux:
            st2.append(aux.pop())
    
    sol = 0
    for i in range(1, n+1):
        if left1[i] > 0:
            a = left1[i] - left2[i]
            b = right1[i] - i
            sol += multiply(a, b, v[i], v[left1[i]])
        if right1[i] < n + 1:
            a = i - left1[i]
            b = right2[i] - right1[i]
            sol += multiply(a, b, v[i], v[right1[i]])
    
    sol %= mod
    print(sol)

if __name__ == "__main__":
    main()

</syntaxhighlight>