from fractions import Fraction as F
from itertools import product

def multiply(p, q):
    v = [0] * (len(p) + len(q) - 1)
    for i, x in enumerate(p):
        for j, y in enumerate(q):
            v[i+j] += x*y
    return v

def inspect(v):
    n = len(v)
    f = [F(x, 90) for x in v]
    assert all(0 <= x <= 1 for x in f)
    assert sum(f) == F(n, 2)

    L = [F(0)]
    for x in f:
        L.append(L[-1] + x)
    T = [L[-1] - L[n-j] for j in range(n+1)]
    U = [max(x, y) for x, y in zip(L, T)]
    ell = [min(x, y) for x, y in zip(L, T)]
    delta = [abs(x-y) for x, y in zip(L, T)]

    R = [
        sum((f[i]*f[i+k] for i in range(n-k)), F(0))
        for k in range(n+1)
    ]
    C = {
        k: F(2, n) * sum(
            (f[i]*(1-f[i+k])
             for i in range(n) if 0 <= i+k < n),
            F(0)
        )
        for k in range(-n, n+1)
    }
    W = [max(C[k], C[-k]) for k in range(n+1)]

    for k in range(n+1):
        assert W[k] == F(2, n)*(U[n-k]-R[k])
        assert W[k] == 1-F(2, n)*(R[k]+ell[k])

    scores = (
        sum(U[1:n]),
        max(U[1:n]),
        sum(delta[1:n]),
        max(delta[1:n])
    )
    return {
        "R": R, "U": U, "delta": delta,
        "W": W, "K": max(W), "scores": scores
    }

p = [3, 5, 5, 2, 5]
q = [2, 7, 3, 6]
av = multiply(p, q)
bv = multiply(p, q[::-1])

assert av == [6,31,54,72,69,71,27,30]
assert bv == [18,39,66,68,81,39,39,10]

a = inspect(av)
b = inspect(bv)

assert a["R"] == b["R"]
assert [r*8100 for r in a["R"]] == [
    20528,18342,15387,10419,6233,2883,1092,180,0
]
assert [w*32400 for w in a["W"]] == [
    11872,13518,13683,13791,11497,8637,4038,2520,0
]
assert [w*32400 for w in b["W"]] == [
    11872,13158,12603,14061,10957,8187,4038,1440,0
]

for ep, eq in product((0, 1), repeat=2):
    pp = p[::-1] if ep else p
    qq = q[::-1] if eq else q
    d = inspect(multiply(pp, qq))
    reference = b if ep != eq else a
    assert d["K"] == reference["K"]
    assert d["U"] == reference["U"]
    assert d["delta"] == reference["delta"]

for m in (1, 16, 32):
    aa = inspect([x for x in av for _ in range(m)])
    bb = inspect([x for x in bv for _ in range(m)])
    n = 8*m

    assert aa["R"] == bb["R"]
    assert aa["K"] == F(4597, 10800)
    assert bb["K"] == F(4687, 10800)
    assert bb["K"]-aa["K"] == F(1, 120)

    assert all(
        bb["delta"][j] < aa["delta"][j]
        for j in range(1, n)
    )
    assert all(
        x < y for x, y in zip(bb["scores"], aa["scores"])
    )
    assert aa["scores"][0] == F(1538*m*m-180*m, 90)
    assert bb["scores"][0] == F(1502*m*m-180*m, 90)

    print(
        "N =", n, ":",
        aa["K"], "<", bb["K"],
        "; increase =", bb["K"]-aa["K"]
    )

print("All exact checks passed.")