Auto comment: topic has been updated by toxik (previous revision, new revision, compare).

edit: strategy was wrong let me rethink

D&C. Check 4 variants (l <= min_poz, max_poz <= c), (с < min_poz, max_poz <= r), (mn_poz <= c, mx_poz > c), (mx_poz <= c, mn_poz > c)

This is definitely a popular task on D&C(I'm sure I've seen it before), you can probably find other implementations

MOD = 10**9 + 7

def compute_cross(l, r, mid, A):
    nR = r - mid
    if nR == 0:
        return 0
        
    minR = [0] * nR
    maxR = [0] * nR
    minR[0] = A[mid + 1]
    maxR[0] = A[mid + 1]
    
    prefix_minR = [0] * (nR + 1)
    prefix_maxR = [0] * (nR + 1)
    prefix_prodR = [0] * (nR + 1)
    
    prefix_minR[1] = minR[0]
    prefix_maxR[1] = maxR[0]
    prefix_prodR[1] = minR[0] * maxR[0] % MOD
    
    for j in range(1, nR):
        idx = mid + 1 + j
        minR[j] = min(minR[j - 1], A[idx])
        maxR[j] = max(maxR[j - 1], A[idx])
        prefix_minR[j + 1] = (prefix_minR[j] + minR[j]) % MOD
        prefix_maxR[j + 1] = (prefix_maxR[j] + maxR[j]) % MOD
        prefix_prodR[j + 1] = (prefix_prodR[j] + minR[j] * maxR[j]) % MOD
    
    total_cross = 0
    j_min_ptr = 0
    j_max_ptr = 0
    minL = A[mid]
    maxL = A[mid]
    
    for i in range(mid, l - 1, -1):
        if i < mid:
            minL = min(minL, A[i])
            maxL = max(maxL, A[i])
        
        while j_min_ptr < nR and minR[j_min_ptr] >= minL:
            j_min_ptr += 1
        while j_max_ptr < nR and maxR[j_max_ptr] <= maxL:
            j_max_ptr += 1
            
        p = min(j_min_ptr, j_max_ptr)
        q = max(j_min_ptr, j_max_ptr)
        
        if p > 0:
            total_cross = (total_cross + minL * maxL % MOD * p) % MOD
        
        if j_min_ptr < j_max_ptr:
            if p < q:
                s_min = (prefix_minR[q] - prefix_minR[p]) % MOD
                total_cross = (total_cross + maxL * s_min) % MOD
        elif j_max_ptr < j_min_ptr:
            if p < q:
                s_max = (prefix_maxR[q] - prefix_maxR[p]) % MOD
                total_cross = (total_cross + minL * s_max) % MOD
        
        if q < nR:
            s_prod = (prefix_prodR[nR] - prefix_prodR[q]) % MOD
            total_cross = (total_cross + s_prod) % MOD

    return total_cross % MOD

def dac(l, r, A):
    if l == r:
        return (A[l] * A[l]) % MOD
        
    mid = (l + r) // 2
    left_sum = dac(l, mid, A)
    right_sum = dac(mid + 1, r, A)
    cross_sum = compute_cross(l, r, mid, A)
    return (left_sum + right_sum + cross_sum) % MOD

def brute_force(A):
    n = len(A)
    total = 0
    for i in range(n):
        current_min = A[i]
        current_max = A[i]
        for j in range(i, n):
            if A[j] < current_min:
                current_min = A[j]
            if A[j] > current_max:
                current_max = A[j]
            total = (total + current_min * current_max) % MOD
    return total

import random
import time
import os

def generate_data(n, filename):
    A = [random.randint(1, 10**6) for _ in range(n)]
    with open(filename, 'w') as f:
        f.write(f"{n}\n")
        f.write(" ".join(map(str, A)))
    return A

def main():
    if not os.path.exists('./artifacts'):
        os.makedirs('./artifacts')
    
    # Generate and verify with n=1000
    n_small = 1000
    print(f"Generating dataset with n={n_small}...")
    A_small = generate_data(n_small, "./artifacts/input.txt")
    
    print("Running D&C solution...")
    start_dac = time.time()
    result_dac = dac(0, n_small - 1, A_small)
    end_dac = time.time()
    print(f"D&C result: {result_dac}, Time: {end_dac - start_dac:.4f} seconds")
    
    print("Running brute-force solution...")
    start_bf = time.time()
    result_bf = brute_force(A_small)
    end_bf = time.time()
    print(f"Brute-force result: {result_bf}, Time: {end_bf - start_bf:.4f} seconds")
    
    if result_dac == result_bf:
        print("Results match!")
    else:
        print("Results do not match! Saving array to './artifacts/debug_array.txt'")
        with open('./artifacts/debug_array.txt', 'w') as f:
            f.write(f"{n_small}\n")
            f.write(" ".join(map(str, A_small)))
    
    # Write D&C result to output
    with open('./artifacts/output.txt', 'w') as f:
        f.write(str(result_dac))
    
    # Stress test with n=100000
    n_large = 100000
    print(f"\nStress test with n={n_large}...")
    A_large = generate_data(n_large, "./artifacts/input_large.txt")
    
    print("Running D&C solution...")
    start_large = time.time()
    result_large = dac(0, n_large - 1, A_large)
    end_large = time.time()
    print(f"Result: {result_large}, Time: {end_large - start_large:.4f} seconds")
    
    with open('./artifacts/output_large.txt', 'w') as f:
        f.write(str(result_large))

if __name__ == "__main__":
    main()