# 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 = (
    "eNrtV3k01vu6N4QyRcZMiQzZ5jLzvr/n8ypECUWUKVEhRXPsNhmKiMwliQgVmkklGUoaFGmguVQ0"
    "StGg3PZ71mmdu/a9a+9z7/3jrLvOH8/6ves7vM/0+TzP881SqsY95EC2NBIRO8pRpp+GKSuyYWhf"
    "iB6ffPx2sQyV1dmoLUtByJc0eHpvRO2iCCw+twVPdK2ws2gG1toCKq6GSEr0g9oCgN1sivfsqXhe"
    "JYuyPVPxq7YhlDuGqSlMFRPfisEyZCIuhbJhFSWH7x1s1OZPwYFZxlhtOQkn5wlgQ68pNgfPRkyb"
    "BK649NLxlHv01eM+tdfcpLWvRmN/YDwllGoxTnvrmR5bTzJo2MN0CSgQS6OU3T5xHLPaZxy7iURo"
    "WWEszT0iTV8DeeicIR/dWXyeec5nQGvTUklH1ZNuG2+wiYhwsZBzvcIq25rO8rUZtBh51q3/u0im"
    "OTAWY1VZIqZ1TCtbiHybVcn2VD/zdWcsMyE/hBILt1Hqio+kWieNgrlasOy0wjhLK4iazsEAny+G"
    "2sPgru0D75454E93hZmWH3asigC/diKuzg1CllAQHgR4QkCJjcN683CVby7sP05BvNOPWIoLoVZ+"
    "KlRnGEOh6xvFvrpO/EviiCftGCXsH4WDrd9JQEgMtRnaSJn0ndaFjIWArRm8Ylk4kuqP4uMGuHtc"
    "CP1p6uCkfSFzJUMEsDSQtmkM+GYIQlq3gw4dv0k5Uv3UGnmS8LWBvmxMom89DL3OjSRdgShy0Yuj"
    "GepJNF1ShExGu1Jk7nQabtlE7tGlFKB0jMxEMmhleDjle6VSo1gVCfkl0fMp8dS0T4iOOU6ikcfu"
    "VNzaSMLTy6hiKJNopz69nB1PN06l09GgDiqsukx+3S0U4LSFfNwbqcFziGxixuHVHh3cUlZAzE1B"
    "lCZKI09bC5IVDlgr6Ar2VFfIx7tA8ZIrDHy8YejjhGdJcyBxxArL5ylhUsQY1MpJQk5eHpsLJLHJ"
    "9zF5x5yly4szfujeS1eFS2hnfxnNH7pMlasy6YzABZqy5AMNJPRT5XYhOJWKookRxAvxF2RsLo4W"
    "8/FY/EwKEjLimKgwQPqx/OgT76K8EGHIXuDBBI+95KlVQg0tK+jxcAQd9DlNci8yiJ8dRQqzPCge"
    "0uT3eCZpt8qQtKkR9acb0eZfLrPVN15mdn78wFh/ZcgjPpUOjnGjkyYTyPGFFVk9cqSiUQdpQWo9"
    "CVakkcqiUhqZk0zhbofJ7MZjKog/Rv6PS6goIJ5kn0+nwOZqmh94nFgP35LD5l4qv9ZLjV9GKGO5"
    "IipZavjOb424uUb48uPbmGwPeeVpUMtYiQXWi7H0oAdsls1Cm5gq1nSaI17UCPWFKkjdrYs1+8ZA"
    "IVwMfqMmYkaAAp7ETII7rziE4/sp/50A7suOxjVFVZhVaYHpVkToEQn8kiMJsfNqmHZQHc2uesjI"
    "UULpVFWMvauK5FOWKLfzgpQ6G1pLHLA4UhuJShNRcFoTSROUsWuOIpo/viLDsjqqmZFGV+PjSfBZ"
    "KDFd2yhtbSfTNK+Oda39CSsw5YzNhSOmdD95Gm1cHE03jERpvZw7ZbM20/Wjl2gq7wV615hDH+4n"
    "0DqlSLI1Okpxx7uInj4j6/5m8vqUTxecdxGvbj3Z1z4nfsk35NLHjzGlPVSEsZh6SwXNUXqYJcfC"
    "jfUaOJCniURtVag80cSzSBs4x7AgvN4GfVkWSHzrhOCSKbjx0Ac+Qg6oe20HxcG52NhpDMXZ7ri8"
    "fjYCN7tgyt7pkHNQgfF6eVRqiaHNXhh9vGPwtEMC24L5oFM0Fm6QwmUdVdgLmuH1MyO8+85C7VQd"
    "TI+djUm6S5BTtgaP0tahKjIMMZZ+2DLdCc+LAnBy/0yE2ZlBsWYStn+WguATMRTGa2LMOjUMKL+h"
    "rjv3Kdv5KHm0DRBnzgVKNztJu6SryDyllOKGimjpqFPEe+USya8rIrbYWYpQ3Ef8D8vJL7OLeKU/"
    "UbyBIgYeSUP5hAHEzY0xPYjByGQ37BvnjdfX5iDadxZaK2dD7oAvhCYvwEXlQDif9sbW1/bYWEhw"
    "22KLntppKDsfDMdvHlAYnAcpf0+M+P2GndpJaM9JgLzDBlz5GoF5/hGoOb8ezgMr4aCyBbEO/kjO"
    "XYqNSiHQXL8Wm5VcIJrCRnfpZNTWa8GIZYR5cQ6wiDNBLv9MWA064WKUCTgDhOPbDTDTSAPzOWw4"
    "+RrjSpMdmFUOKC//UTPcgsE7Mg/jkvyQJuuEqpgfeNzDxjs/B1xvnA2J8cbIXW2K7dfFsWipLI4I"
    "15OuRj7hXhptCjZh5EzWWv7eI8aVlZmIZhczB85dYPQdE9l7NNOsFm8SIHEDe7qoFUFK+Umk/vQa"
    "SY+cp295qrB8+Jk83sggYoMKNt4UgfqCiUgRUMODgnEotJgEP0UNWP7Ia9dYWyiQDoys7HB/oSUe"
    "vTKErCwblz9qYbeRHso9gbAVtug46YitOcuhdDoMB++GQ8DUD7Vbp4EvMACDNWGQLIiEj24unskk"
    "o/u3rcgb2Yw7whvhrj4fZqd9IPrFCtuC7FHMYwGRwBnY0LEAA3U2sHNcBv9sZ/CXsXCiyRwzun2g"
    "rBmD3OP+EH7pA8X0WLhGpEKqMxpy/AHgv6YL2ycqaDzgj+rZJoiYqIjU7XywHq+Hp7/ept9jpft0"
    "ounfe+s/K1vu8TNu47zp4puttPz6Ynp7qYZWlm0hb5NMwpYU4kk/TS/GdjJ31iyi28sFqW6uIGOU"
    "sJcqHnUx2wLD6MtKecxKa6A5PhX0vH48SW9pY2JHGilIQRQPjK2RO9hDcbflULLYADXqTym0Rhki"
    "xvdIVUqJpsWuZtv1HmG2sM4zhtdiiMeNyG1sEXPoWQklqJbTyB5FqD4zhk35USpOGaRRYvqYYK+D"
    "Wj4fLHoXjqE1kyFiZIBPm9XgoQF8KnpJ0uqC2HlAmjkk2sdcYZ2lRhkJxjs6nxunG3kzSbaxjXa3"
    "lZD9ZxEkuxhBP28ujO6tQ2f2ejSM2QD56btgZ12OcaENuB1TgW/J+yH0Wz70ow5gVOg+0EA1zh5q"
    "QPWBgzAebsRqux24fiEeb6sCMS49Gw8UPDHhyAFGIkwWn/j2YPWoaFQbT0DMylCapxdML+WzsWjt"
    "HkZVCayBRGW48bzj2la50hY2+y3BU6aBYYMh+vZFC1HlV0m7UwwdoQOkp7uHHq3gRej+e7TNVx9f"
    "1ytAKp4HqsG1pHO/k94cjqXEh/EkVpDPnjyPmILwAtJuliXTl0PsIPEomzHtsczOyjomf5UVdw47"
    "0h/A2D8vZdYkNpP1MSVyWJjB/BlWNO5eZ87XttLekCbGMCQL3sZZ8OV3ho59IB2fn871w/3RYia0"
    "MY2YGyK0/NcA1t/vRjppMm93hbMv3SiG7K2TcOKLAn/XBqqtM/2p9yGrhYmTyGS0HJ8zwRccqLHn"
    "NRNje5oeFSbRJ5scUsN8qnY+wBy5/5a5a1XCfNTaThpPQ5jpDZJc3W5rZGx+/0p82WftomhMY/a3"
    "MEmLZKhG+BBzPmCI6c+1oIzi3ewgQSP6pViX+r2ukfuNu0y7VTTjeaiA/fvdntRl7L/bk/Hr5J+2"
    "FXi5cde/C5xiL03PYTKVGObuHCWu3ttrrKiln0MiykS5q10ZX9YMhjXLgymou858m3+JPWl7Ovd/"
    "nBLWWpirZjEKPk9+6hixPMj6n3L3d0kdxWP5UkzU4q+cfTjqq9lfOXe/sd6i6uh2VoOCN71pcCf5"
    "6HTSkX3HiPOEMCGDkfSLoxI9aOnj+iCV38ksPM1DV+bu/+lT35VcchZQoydKQjDfHkpSRnvI3eAy"
    "lQQ+oKmtv+CLWRu9PLucHCVuksWuIKpvHiZhKzmI1u2kQMVjDPtyDb0yPEwzzwjhoxtD4Qru9KDH"
    "inERDaO90Z9ooFUDwQ1PSSv3EZ1IOUddjkdp6ukL1GD/jmz1ikjcuZ5E5BzJZXs1mXtJ0SLWUdI6"
    "kEI5Srdp55diSt5zh7SSL5L3w0ZqO9tOCfJ7Sav1Jg3/0kJqFmeoXaWKAnoLSeisDzWEt5CLXwV5"
    "ND6gvRpXmCnVe2jx1S2kNEEAkifE0c3Li/cjR2gzyeDU91c0tnQS+EUe046hDuLXXUFZghfo88UC"
    "shPvpwbspNinZhScZU3Nk+MYg7OHad1wMqX23aTZcYdJtKSZjGdUElXeooaNGVR/5cdskZ9K1eLl"
    "JF8VT9Las2hGfgmVd3hTnbQDta+fS1kSSfT1JIseKJdRYctWYnXn0vjt+eR3p5RK5Fspa2Ye/epd"
    "SrK1JTSmv4ImnjhFOz71UPfMVFonEUG8PZqUdqGePlfGUd+js+TyYiG1tXpRzaoqyu76SnO9X9HL"
    "8Z3026adZN67jc4GvqO0Ha9IUr6BDqlnknjSCeaOfDkZV+6l/LsHyDZThgxdxUlULouMVlXQ/dUt"
    "FBd0hPI+F9L6R+dpzIMGkmW/IPmIO6Shk0uftbNpnHImBUQkUspvFXTl0EIK4t1ODU/lybBqJa1a"
    "tpTK2peQj34Ofe7MoFae1RRsXEXnXowhk7ufqGlAn4Y+nCTe5GmM0Osoqr+9kJn7Yw69+SGU6bTz"
    "ZU5OVmA/vl3LRGnlMzmCE2lbrwwTudPdfK1uANXqnLBZfn06lcteYWIfVrD3Kd5h2L/Z/cCqKcl+"
    "4uNyO5ff8GcN0Ht3jTFJec2WvqptvvepDLuAdx53LxGx9I/8mVMtSlXfZxKvSCFTyb+b2TDpI5cb"
    "Sxxf2PxvuP5v+deT++U5NtUvOs3ERqezH42TY/4VbPJKHM/+szMuPGHs/fPesT6wimntmy6Scn5B"
    "SuP3UHufFNCjg8MbZpNvvjKONB1nMpWzia2VQuy9ZtQ90kZLEppIJOMxVQ+MwbQBdUwMC8fDWy54"
    "kxOKL/52+DLExgeRDZjQYouNHXE4csobGpOek5j6LLA6pZB0u5KZrOQEkzPWyBedhij2e9JykcX1"
    "hUnwCJ+Ca46lkM6LQSnvCjjdC8H19SugEeaB2w+jYftmOZqF7CE0aIWaVndU796Fc/xr8btPp/Mk"
    "sbpvHv14RcL2SjC65bbBoPcU5Lyq8LS2BKkPz8GsLxmZv9ZC7UwfWfpFwsL7x1slyw7u1zvR61wH"
    "mYzd2H82Ac67wslc24fJDNJFju1hnEEmlDedg59jCNbPuo0rVSpoaUzHUmEZqN+SwRIRTyr+Vsiu"
    "LDv2n2rB8M1Wbn+/O0MWmhkj+LSOl7NaTZTTUDSVo3iq+OdZ68IKUjNQx7WONdDIXY1n79vwdeM0"
    "uCeugXxvPlz7s3A6+g7Kf2nEypW6GNukQ4J9BJllLrjRL4y6q8mU483D+PLHkOfrKNxy0qM4/35a"
    "tnw8dJOVmAHxBAjsGwXBayKQaI8z+e9wUbHCm7uXF8THZEu+sww+lEpuS1aie/Z4hq9Qjdn36gUV"
    "tTaQs70iS3H0lj/gzF/vxh9mke0Hb/2ccXqEvuP9bi/2hOZqJkpBkhPmNoZjwjiSV8sC7Ni1ES9H"
    "b+Jy6NC0aG5sXIe3/YwR6uRxb8ENmta7j7sWHjzMnM58QmETlUhFzYvRh6f1m2g2+Wb/Ef/+C7ws"
    "/4wTLwcOsEV8uum16HLsoGYqsbtuE9ZaDfGHdrBccRRntMRRs0cdCUppiFIJwt2VwN2zPFCT5UDZ"
    "WJNRd/pACYveU3HuF/bxwPFI61mOcv1t6PLIQIN2C50IPE+FIUuo9Jk8Wt8dw9aFsSgVcsTo+iFm"
    "fkYBVSwMwlwpT6zLS4dBSgMxmr7oLlPBQIgDIC6Pf7Q1bJ+m5YlX1fTI25OSgj+SyW0ZLHs4B7M6"
    "xGF/sZ0c3eQoUdwMzVLTwXPcGjYvOdhV1GCzKsyRGzt/jQYy2uLH/a183pf084u5OTr0aAVd7NYm"
    "gVAtCi6Opr9Sby65r7O4HRnAzbvVGi2LO22dTIxlHmnqbeferzXbxv7/UOtDR9dxMRTFu495PVqA"
    "9SFKklTnbv0Zo6miZUy4zRMb+Ty+f7oPrBW/YBk1EEIyQbbm/yr+jlbptvx3j//nxXx5PEvRtuMn"
    "Bja2FrOj7F0Zra8P/xQXrpra5lbb3v077v+NWCw1NEtzOW8u1XKEzl6c/oNvXn/j3w6P/zK2epwa"
    "CsiJs7LOHOTuO4pXmHIE2yktbB77g0WcjX2wPncmnySSg1Om6tw61VGsSVdHf6PABTY236fEosdi"
    "kDldtZurx8BInaRbDlD7cAw5r4ji3j14eQ0rQaeTVvVtp9tLOilyfC/3rNLox6TZEU+3RHWwLDsA"
    "pu6jER49FXodWUzMYDzzYtzf3g22r89SUM0jdkr8XXKeUcXkv2v5mX9hk0+UkHmIbM+b4PM0YbAf"
    "zIb7vfd0UmiE5ZETwNX/8X2teZO84r8x8xfE8WsB1uzdDZbUC7TsTsOCLbkYuVjJ7a0bHDZhdk0/"
    "Nyda7lOIKSizCdHpMvm/0v1rvT9r+LoFS/9cjNm2+c7WGoNTaEhDj1VnasIxLzbnBLe+RqW7Kaf+"
    "x5xqa9uHQKnJnKqmTkiWHMJLpWxk1Zog+cZbeEvchN3IRM4z9jcmxknBZuEGD4ZPowguwoNINbxo"
    "KnkpCxWDxhBQ1ONo7g3nXKq14VzqO2zDFPTigupodLTpcWbeMuNohZ7+OVNMG16Gc7FNaOIM0KoT"
    "ftz1XutetnLvF1r2RhbT27Q5uk11EJs1g8O6840bo4m8IQzvR/WfvHvpGmg1e4Kk9WaBIfS6mHPy"
    "1mZzIjZlYKPHMPzXqXBs9ncxIyc0LRvGK/yBq5Of1XF1BkVZc5ZtfcDZsczX9j8AVrxl9A=="
)


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