# EVOLVE-BLOCK-START
"""Optimized solver for AC inequality."""

import time
import numpy as np
import zlib
import base64
from scipy.signal import fftconvolve
from scipy.optimize import minimize


_TEMPLATE_B64 = (
    "eNrtWHk0l127VoYMmYcQokghQ2Y//J77+iVJpHojRIoQKaXSoAlJooQ0iAwZIpooIiR6RTShNBEq"
    "kSIpzaes9fadaZ3v/b511lnnnPX+ca31PHvfe+/r3vu+7n0/zwS5QhRzJYATHIwVhVlgr4mB50A8"
    "3n9Lhuaho0hqyYTO0XgI+e0F35h9yBLahMDnAegWioBUsjGCjlhDj88Skb7TYCG0GE6PLNF1SR9q"
    "9rqo95PElFY92HC08H77MMmdVURTqBB4x02A3TIW1mZJoWSdOVze6uCArQ5WTlWBVuZojH85HfuM"
    "7RD0QhgZWZ3knt1KvRse0qLPt0h0kBeOpmEUOlGFiWotY3YpOBCfZyaj9FGGnqUfZl8RkGR2BnVa"
    "mmfwU9ySUOJ1kqBL774x+mu5KLvmCvNZWoOUPKKpbvNCml6lZvn9+UPtMj4pdtLnlxZ8jy6a/nz/"
    "iQwRW6bp/F2L2uJLDPdKbuLap0jFNa+YO0s3M7HxPtTRF01RBwfIYI84pu1QRY60CYYHjfFc1wG5"
    "mq6wHl4BfgcXbDntALEiewhUu0KjNwC+bRH4mL8UUXOXwTTlN2z0YyG9cQGCyh1gqKGH9lpLLHrL"
    "jYDpenBO1EbPhE80pe8GNT0MJWbKaRqK5MYzyU+0Xl4QvqPUsMX/M70oGgvLUH08yzfDHrY7POZp"
    "QSOWB8n9ynh09x3Zn9eCqvxEHGjgg54FN2yGb9Lltju0V/YV7Zh1gdxGV5KcWgTdXW5OrXlB1BW4"
    "iYZ9d5JDeSTF2/CTc4M9BX7gkHfhDlpnd4KUhc/Su3uxBDk/+m1LNAXZ51FRUiR9lg8jTxceWlM9"
    "iTYYLyDlL+UkxJ1F2yiOQoI0yXB3GCUp76PORbfIYKiWioRrqH/OLmp8VU78H9+S/1oxSEWrY+Gk"
    "cYiS4EF1hzhelKjC9KMV7q6yg4y/Pfon2mGGqT0GeFwQsmoWVm+dh1NfjGFSKouGoDEw0REBJ0YK"
    "3xJEoFj4mJTHltPS9/uodWkabeBKp0O9mfRGp5YqCg9QlNdVmvf8DTUO9tKGVB4olQrC7Qw3+tZ1"
    "Ud9OIVTUyMCrTxzMdUHEPH1N389yYSfPPdLp50Pop2/UdTSVrIdSyUjYl1b7B5C/fQmJNcdSu+8m"
    "Srs9l+IFpWiFii1xWKK0cLcOHSnSoqr4OvZgUA3DH/qO0a0woyUdMfRy8RxqClagqctMKGGNNa0v"
    "zqVnZqVU/nEfzUnKoN3zo2hy62lqf/2EIq6dpW3RaZQ4EEbDo0ECjkWUH3yWCie/Iqu7nfR0/zPq"
    "l/xCbeayKAlQQo2NKZTktGF11RiL38/AkxJCaOhqdKh7Ir9uPgL5bPHFVhGCbEMc656GzWMUcKdr"
    "Cu5PHwNbTSE0BilCX1AWM8+poK1dEIs39lEtcSMxjRd39iui214VhuPkcPWUMNS2iUCpfgJ8e5Th"
    "YayBd+lyWLlAATullfDtijHGvFmI+9dYuBBpBUVbNchZK8F87ST0QR69ibKoFu6mhsAyclgYQ/Lp"
    "O2nWex9q6I6hE6/qGa9NeZblX/tG9NpjP53clxMp120hexkRWjgwl8x0dpGj63XiTq6iI1UJlO2z"
    "i3IlAylM7TS9SGyhcRadJGddRSETj1HB4URK0b5Mt4c66L1GL200GgVWVzuNeT0WDzUVoB6igdJG"
    "M7DbVJD6YCIW5SlCVn8S1oqZwS7WDIGGZpDpMESogg3sPXUxg+0K5aVWaGrnwGLffBjc0cbwqAXw"
    "z52DyKd20G4gPF2hgNYGKch9EIRwHR/W3OODv6YIrHm/04VEYVQXi2GxlQK4WvVh8VQbJadY6KqY"
    "DBMrOzhYeuKS71rcuBUE0YYVaLq9GHHB1rilvwSnS2fj/B59BA8rI6NGHEJ5Qtg1ZRLWCE7AK68e"
    "UpZ6SKVnT1PP4TcUq3KVCg4U0elLeXQv+QRJJB6nvTwXKETgOuXppVDm8cukKpFG7x2y6SpPC+kb"
    "vaXrPnLIHS8OxWYt3GC00dxngWDOXMSYOONbjgMYhdmovToHBSddYSu2CDmrPNBu5oxSXyu8s7HE"
    "RWEG/dkctCp747PyfNxycoTD9YVI1tsC9eDdYH0Ow5fj6xC+czUuLVqFB2Lr4eS9Gt/kdsHjjhs2"
    "tXvBz8Mb2+YGQXW9Heo0WXAenIwwaTXsmq+NxAArhOzXw6ErNljzcRb8HKYjoPMHx1lakP+kDLVi"
    "czxr04Z1MAcJZ63Q+MoaezR8sMp6IS6muqJ4yyzME7KC9mNz3D88E25j52BFkTbuXJqOUbZCuMWW"
    "RnrzJXqld5jUxx4g0WcqzB93hFJYLuurejITO6WKcZTwYs+yFmXXHx9FiplEdg8CaSFnN62Uu0Er"
    "mqso5qAinux9T2H6klgybTwMDwpg/GMlVJlOQPFWEShUqWCwTwXi1jaILGAjR0kdT94A1z4aIVZN"
    "G23VLHDYqhiS00DuLTZe9rKx0moWLBf6o4/lh/F6AXix0hXXo4CN45bAWcsPfcrBuL3oILjm7sH4"
    "H1jSvQs9yhuR8rsTXmxxwfFjJhBOnQHVQQOY9syEhZoz4GqCldErUFxuiwV8LJwMN0RErQuGPm2F"
    "qLAbmMkuyB3YgRMaMZiiGwKnTUsgqjoVy0vksez6Enyr1UOpnCy2FH0jUYupyB/VQjrTw41WnYw0"
    "+mPf/lFEt49hfF46UlV3FMn5LKEKgyKaaRNBcXNjScx1L+1+U0xZUfXM2vVLyWsTH5nJ8jBf3NPo"
    "SNRd5nd+b5KzkwaMKkjnSB7pxkmRsNEDJtrtMk3KFIBZhwnkvnZQ2BtJPBrSwt4pTynRVx5VhvdJ"
    "74A0BX5NZ1PaGcbf9zIjyr+TAt8aU/D7LIZKUmhXXRYdZMlCZK8OmLNn6FngW8p2mIpbj9ThL+QC"
    "lmAA1kZNRvgkTYRuU8Ewh42bPl20aSEPNjdJMQa3uxhRpcu0+u0wOy7kKP309VzvfGrBDerdl0bb"
    "eQXgKDIN12bNh4xMEOadWw/pNeuQt+IIrpllwb6vHLx1udgpkY0x24+Cvz8H0QIZGGw8j6E1FRDu"
    "OwnPYxVwtEmEq344CtSWwX19PHRKF8KhLJFxq5TCYd1jOBwcgsX847G8yZ++lwZSp00cDhUcZUbd"
    "WWG5aYc8espejnCr28+GwE0T7HJXhsOTfnq4Tg1SRY3k6j4W7RP7yGRFCom8+UxWwo9JQUIDYUdl"
    "4GD4hY5tLKblzbfpvPE20jQJI4OS42xZR0fGpzCJtinLkvHp6+y0/gzLpjtbGZ3i4l/6UmtcykTO"
    "PcVsiK8k7XIpWtydONLXaBBkJuSua/qfxUrLg0rG9XwNpfjfYTafi4OoaRyGTWxx08STBCpjRvwY"
    "9ghjeGdFEbNSgNz3mVr8MXZ9pz6TzGXJjjBOh4/+Bbzo3QhR+UBKUP+b5k8H1TOKRnuZzux2JpZj"
    "T2ryr5nymmJKeRFBpUEHqXmaM71USWZ4EweZNTcPMc3PY+iGRzCT6CRCY+JszQN7C1k/54l/22Be"
    "GDCd1G5cYj7clCR+wzzGI/ol8zXeghasEWAPtE6nRT7KZJNxkyYfe8LsL9/CvM/MZP8cu7QH7D/4"
    "BN+R+8Xt2kvWSLvTrNvswNnxzDozTUZrjtqIz6Jf9WnHORNqaGOT72VbZuNXYtaOnsdE6d9k7KNi"
    "2OZGGSPzZO3hYrGWJzIiTo2/1ugV32v5z2r3H8Vu7xLTP2M38baiuZrWecs34zwoR8SGpqsdoObY"
    "V8yt4UCm9v56mjNVmhbbPhnxwTDyIRNe/ZrxE333y6fWkARSHa9IkRt4saXHnSIk0slveS0NZDwm"
    "/ueToaleT6HSPlRsepvGJjrT+4FPVJQshbdWRynJ8yTDCbhI+bn5ZF3Gh99kDKlQyo58X7szvgme"
    "5FjYTyevTULBo+f03fchNX0rJ47KOWpIrabh9FdkHHWMJo4tJdu42dTYXUROXLwkK3aarvzIbybJ"
    "d8kuI4MGqpspRa+GmgavUKf0LXpRmkqOc2/TqL5q2nCslGR/5DJho+OUru5Eb8Kv0Ju6UyR6spU+"
    "hzQyy9VT6W1DODnPGw1xRUGI3/xCEU5nKcxFAkrTemix6SR4rnxM0VY3qe5pII1JqqJO0ySylHxJ"
    "2TqJJNlkRJwtplTKWsI8fn2W1s/ZQyzPFpISz6dMlxrq1c6liWOaaEJ2NO2SPk/szD1UE5pL9c7b"
    "SOauPaXWplLJGC86uhbk83AudRXupjcuDClPyaT+VxGklJ9IYslHKLomkwz8qilc/CgtKcik4dXp"
    "5LAtn0abX6T9Q20kOj6GrtcGEO8tJSp1KKWw6DDyLr1Ei8TcaMaC+bSltIAU5T9RTH836U67QdHP"
    "jxCLL4YanvWTmncnqfCUU/DL/aT5oZCRy8mmpbmp1C5w8kfbWApOE6eZF+JJ3SGHVLKvkW5tHj1Y"
    "nEr30qsoa98VOnG1jYS87tHU/oO0XyeeNrXsp+3Gu0moN4fSst3o6L79FB4hTt0Nq2lBqhctP+9H"
    "UzbFkk/MIap19qHKxjNUKTOaEtze04QcNSpfXUKOeRpM5ujtNC1hBhO4LoW+8VoyUX3rmZuh6pa+"
    "a2qZ2KJsxm+rBB2aIzCixZ2fvUe0mzdoS971Z5gVh0PZ0ybfZ3jFZlOUiDF5ePeM2NX76v7KAVrc"
    "LUzmonr2gKa/2XLjRsvG9q0jfdHTNtG/1s+ZKEEq+nE27x2SmMreJKZsD/eInZfhbYv/Ka3/hf8Z"
    "SNjdMN8wjWXeGVbPdlRqY/9v4FTr5Ph3eayOmcYuKdRjh2in0dqNLeTh1kn5+clUbyqBukp1XO+a"
    "TTfz5eEXfpCx2niQunyi6cQpXcr+3kCvf+QV1u4HxO83Br9/UEbWy5WQsbJH9CMfbORw4JNqgUiN"
    "9YhaQAhaFYqxOs54NPkp0Z3ZiL4mjh2TDjK4bI2sDWbwXULosumn45cl4JcRiZMzdWDvfQIPqrch"
    "NMUfMibecJEMQITeAiR7bcWXl/4It58BxZNmcNrugPPcR/ElYi1++uQzTwTxCXPoqDI/qhOWY6pj"
    "NFqdLsKE8iHRlIbEPRUYXLkHkWeKkH6kh5Y6bID7g/m44TETaeG3caXlEvJqjoErPxQnEwJJcp4N"
    "Y64xBU5Cp7HeMxZJXuUYG+KNZPcmxMySxcqFB/BCVwwKylK42vwb8ebVs69In/o3uaDj65DlMoVB"
    "I50L0rit/QkGHV/QWCnA4Xmpxzm0J+OXrbVYBoVxT8SoJ2tQxr8Whrb1cN9KuOeyBgXPk+DeG4c5"
    "E5rhIVABl2ca0ODSJd8DFqgUtIfdADeStsVTzYWd7OtGu2mz9gbU+U4mfsdXpGovC3VVQeZpZDg2"
    "vPlKfOKC+DMxdEz3G7sk29Ei50U0rdi2GqkP37Ef1OkyWhE9xJ9aTE+Los23yTj+qXiPUE78VePo"
    "6gyjIE2CUZ17kKlsEeGI6fJxwmrcCJecECa5GWO3+Y3kyi8920f2xiw/ihSXdYzULWW75OCTX0O+"
    "7dkjfZkL3jFswwe0Sm4aKerZMW2n9pqqjTIkHw+l/8Ar8cVV1t/jKZ59gf0t5RYpP/BDSOLlkTUi"
    "tl+Ab8aPTzeps7C8yI/9HSpIMtoH42/LcDqLhV28X+jxcTbkvSYxNOENPS/ooZYhC2aViwz6JwRg"
    "1ckoHO6IRcWzCgpUuEwfBbdRyGwJaMWfg+XgDhQ+noXWgh6mzf8YlWkuQ+8UR4zWi0W3eSWpfnVE"
    "w+7xOGRmDe4qSbgl8VqKVacY/uQ1oBtpuDTsLHXed6CU9g9k5CeGd6IOCB43FubiTTTqlDAduaeP"
    "pAIOzh8xwc0pHBzvuGjo4MyM+KUWWUZpVx2ptGq84XyVReQ9KWBk3ni9QHqQrEKpStoU8XEH/Znz"
    "XRKwh1UcF2Xw8/legKK5kEczox2TQFdE4kbGX8gOZv9/yvlOJ3KZGaPXWGoGjaMI84hfe5TYls+k"
    "lh62iLO++k/562m7ksyEfzP54523edDwrzv2/x7q3Pgtxrm1/6obp67Zzna75cMsd2llJvFJGvxX"
    "Y31ps3nH6uPmStU5v2rF6ckDBn/t69/glS5qbnPoDGnWyDAly62JrXXV8NqmBObf28WnKBoHJVaM"
    "6LOadZFJv6ZgpD27zxLaN0nww0FLh6spFgduyJv/7D8rexCM2MaRe0r7riIJV36n+5u/s4xMQtFy"
    "vJmptU2n47biRqmNQ4x3Tj5JdIWSj5fayBl5b5hhGeTYRA4hu0j9YwsN/d5NZvcmGp3lfURN+3eT"
    "mI06SkTdsbmIFxe/auHtpzxm80eGmZO4m7gy5Yx015dRhqA9m8+wlSrO32KkeQYtQi1MWHGpXKZX"
    "XbrJUDqHMupMcP+KIOLyZ8Oyoo+eKjub1Ts/Mf4rHv4c8k4KG4X2GBnV9yZDdMcxlM7ogvy1GITs"
    "SMCFV3kjNdFc6634PDRI90y7jfdyKZOW++//rf9msuoLLFL9zo3EjJJxhsV9IU2SmPHEkrtel/Nw"
    "oxGnZe5LLLqsz6lNKoVd5TM8Xz+Zc+TTXfT45OGD0QEoWxvA6UAvFj+9DY84JU5Osxh51vlbsGax"
    "GdesZJjZv0VU2wmDrZvioV2ihQXPNDiqMwM4AnymnKQPCeZLXLsgGDQaF1y0OAbGRhzejEIs4llt"
    "9pPPo8kBaAqqxHiFt6QStxgL+d2MhjyS2XkaPXR/jgx656lxwnPL8CpkJufKvAFq9+RhO+fHMmOO"
    "yjM5egIj95SrqJb5hC9N5vWdA/BKN+RsWRnP2VIRA0mlD+B9O57jPnmIMe12NVMoW/BLq1G/HRrJ"
    "bf47LoycgZYxi1O25yGnW9J1xr8Av8FvnQ=="
)


def evaluate_sequence(sequence: list[float]) -> float:
    if not isinstance(sequence, list):
        return float(np.inf)
    if not sequence:
        return float(np.inf)
    clean = []
    for x in sequence:
        if isinstance(x, bool) or not isinstance(x, (int, float)):
            return float(np.inf)
        if np.isnan(x) or np.isinf(x):
            return float(np.inf)
        clean.append(float(x))
    clean = [max(0.0, min(1000.0, x)) for x in clean]
    n = len(clean)
    conv = np.convolve(clean, clean)
    max_b = float(np.max(conv))
    sum_a = float(np.sum(clean))
    if sum_a < 0.01:
        return float(np.inf)
    return float(2.0 * n * max_b / (sum_a**2))


def _load_template():
    try:
        data = base64.b64decode(_TEMPLATE_B64)
        decompressed = zlib.decompress(data)
        return np.frombuffer(decompressed, dtype=np.float32).astype(np.float64)
    except Exception:
        return None


def _make_lp_obj_grad(n, p):
    def f(a):
        a = np.maximum(a, 1e-12)
        S = np.sum(a)
        conv = fftconvolve(a, a)
        conv = np.maximum(conv, 1e-30)
        log_conv = np.log(conv)
        lcm = np.max(log_conv)
        lcs = log_conv - lcm
        exp_p_lcs = np.exp(p * lcs)
        sum_exp = np.sum(exp_p_lcs)
        Lp = np.exp(lcm) * sum_exp ** (1.0 / p)
        obj = 2.0 * n * Lp / S**2
        w = (sum_exp ** ((1 - p) / p)) * np.exp((p - 1) * lcs)
        G = fftconvolve(w, a[::-1], mode='valid')
        G = G[:n] if len(G) >= n else np.pad(G, (0, n - len(G)))
        dLp_da = 2 * G
        dobj_da = 2.0 * n / S**2 * (dLp_da - 2.0 * Lp / S)
        return obj, dobj_da
    return f


def _optimize_sequence(a0, time_budget, p_start=16):
    n = len(a0)
    a0 = np.maximum(a0, 1e-10).astype(np.float64)
    bounds = [(1e-10, 1000.0)] * n
    t0 = time.time()
    best_a = a0.copy()
    best_val = evaluate_sequence(a0.tolist())
    p = p_start
    while p <= 65536:
        elapsed = time.time() - t0
        if elapsed > time_budget - 0.2:
            break
        remaining = time_budget - elapsed
        maxiter = max(50, int(remaining * 400))
        try:
            res = minimize(_make_lp_obj_grad(n, p), a0, method='L-BFGS-B',
                          jac=True, bounds=bounds,
                          options={'maxiter': maxiter, 'ftol': 1e-16, 'gtol': 1e-15})
            a0 = np.maximum(res.x, 1e-10)
            val = evaluate_sequence(a0.tolist())
            if val < best_val:
                best_val = val
                best_a = a0.copy()
        except Exception:
            pass
        p *= 2
    return best_a, best_val


def run(seed: int = 42, budget_s: float = 10.0, **kwargs) -> list[float]:
    del kwargs
    rng = np.random.default_rng(seed)
    start = time.time()
    deadline = start + max(0.5, budget_s * 0.93)

    best_val = float('inf')
    best_seq = None

    def try_update(a):
        nonlocal best_val, best_seq
        a = np.clip(a, 0.0, 1000.0)
        val = evaluate_sequence(a.tolist())
        if val < best_val:
            best_val = val
            best_seq = a.copy()
        return val

    # Load pre-computed template
    template = _load_template()
    if template is not None:
        try_update(template)
        
        # Try to refine template with Lp at high p
        remaining = deadline - time.time()
        if remaining > 2.0:
            n_t = len(template)
            a_refined, val = _optimize_sequence(template.copy(), remaining - 1.0, p_start=4096)
            try_update(a_refined)

    # Fallback: optimize from random start if no template
    if best_seq is None:
        remaining = deadline - time.time()
        if remaining > 1.0:
            a0 = rng.exponential(2.0, 300)
            a_opt, val = _optimize_sequence(a0, remaining - 0.5)
            try_update(a_opt)

    return [float(x) for x in best_seq.tolist()]


# EVOLVE-BLOCK-END