# EVOLVE-BLOCK-START
"""Optimized solver for AC inequality.
Uses a pre-optimized template found by progressive Lp-norm gradient descent.
Online refinement with perturbation + Lp optimization."""

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


_TEMPLATE_B64 = (
    "eNrtWHk011vXl0KhSYYyVSRDUiKV6bs/X1ODqS6plCEUUkilKGUIGTKGhOSSQiIZKsmcoSgNRGkg"
    "zelWt8Fwvd3fXbf13vfeZ633Wc/zx7ue9/6x1znfffY5Z5+9P3uffb67N9ixI31dKk/UTNlROaHa"
    "9y8astLtElRRQ+ythLVw8FRgpSdsBr+6GjtabAwmZomwtsG2eK+5hPU/50hFBbJsi0UOqQyPZd9W"
    "DtEU+XFs2i5haEeXY6maANy2nIR3thB6zdIhr6qIIWF/nAvsoNW7cvBmyz60D8bBvigOPS+PonSZ"
    "Bzq2B6Bxdha4vkSjZlEI7ia4weYQN6bNkcRufh16OHEVftW3vkCEyT8VS68+BNKCzW66+3Iq6Vf+"
    "6/BoTsu2p5FV1DbqVzpLvMkvSbGkmEk4JErPSi8xLxK6mF9lGo2X6/za/k5n249z+FuLpajZIZWp"
    "Mqujwa0NTOOjw/TCSQoLmmfT1k88mMQtp1O/bT4kZI7QhTxP9CgL4WSqJ4K+6uOh8SloOO+C5ZVG"
    "+JVEYHHUa5Q6RqFL5Gfo3kiHf8o7LBsOxm08QptoGG6MnMD95ccx1SgSNpODUZKwFwd03HFV1R0e"
    "7ivx5L0n/K/7orqvht4Z7sdUmfFIW5eBprE/U9OcCqyXGY01D3Jw+dBieF7IxJyeFegM8YK/8nZc"
    "7zHGrC+rkf8kCEbGxjjUZYZyueXQstiOrmRtHKiwATc+0cTwuejyuUMXM0chTr2CcuoUqfBiNLVo"
    "GlHWvLf07s1Jpi//GlUHbSKptJMkVdpKW9TSqDzvC7ExJbT/sypmu6iSJ68cuKV3U7mBHuRPP2LC"
    "BmbA0HCYKV7Eh5xzk8mobR5ym83pWedYOCuHk07/cjTu6KDJXD+AS+o9TWpeC7HhBShIDcOJCX64"
    "cjMQC24fwPCuM9i32wVORwvwbFIgrhWcxMfIHxAvXoAzPmFIastGbH047PeEo/LbmS1idqLbnLA0"
    "djvKz7+nUm9nrPK6SOLOZlh44AuJPbeArCYvCmMnIWmpIg64iSAyQw8THDago9oG7w5vxPCtmZg3"
    "IxTxMc9o2ctoCHpLYPNDd+x9y4/G8CXoS9bC7OmvKeeMFiw/3SRhqTc036uCBHddpv0zO8jvczC5"
    "nTlD266cI9HntkxQ5TLaWbqOqYrIoIZp7cyQfyFJDrhQn/tKKlQeoEKHYJKyF0DWzmCqWzAHMeI/"
    "0g/PhMDn0kVCQ1PBe7eALGaJY971MkpuksX84+YktWc5bC7LUXTMChSuPEJR471RP6qdukXCsCPX"
    "ANtuxyB56jqYzMxBWaIvrATTkTQ2BCse5eGeagDMNmQiVjgaz6/HodY0Bgrrg1HN44+MRXsRX+uG"
    "U3QINXNMsbHXB9l3rMGtboFLV20RmeaOgnkHUHdTHyfWOaPaYgdch0xh/jEUrzw34qLVIcQoW+LW"
    "1Xg4z4nBirFHcONYAmxzD6LjeRpcRpyh2XAY9rtWIiFlKc5sAna+2AhdFR7Uv9TAxMZW8jUZodlc"
    "RuT4fC7uhzUzq8/e5sS1pfEFqvF4wnhdaKDKbfG0fV8AlTzgJw/vGpo20Y5EonjgKLCWTtZOxeFl"
    "cylZQBofLwsjdIcBYhxX4M5WQZQ3HIDeVB6U9x9EwbA4EpX84Sj2lFZ/8sDM5lnoytsLHhlDZDWF"
    "QV19GRJehcG5bQu6MtIxON4ZoaEFiNTzw4NdF+F3IxR+R+/immMYjObUw1o/COvicpCYuwV79qVg"
    "lq8V8rJ2YcrahRgZFwyX61ZIU9mLrOL90KvbA2V1WzyYGgyZ9Ehcq4xF2MwIfL2SjLVinli9IhMO"
    "TiH4+sMVxBWEYfjoOahODEbruzzsFtiHNbGX8E41BMZZUcieFgbxC/6oqDmEK7O9kTjGH1K8C6Ai"
    "qoGr9yYimX+E+FY30pqf20l0XAmFr2mlcQ2nyXK6MqaP66KezwqY2TYNQ5fUUf/ZAGLuuuA9Gg3J"
    "+d/8vjkZC9/7I3pMFpzsv+W03iy8SjqGFtNY7Fj9I3zsjsOn5ihypeKROpiB/FvHMHZnEsYr5cG3"
    "/hQyX5zCGPcSLJLNgVDHRaw8HwEe61b4H8iDYEcjboTV4uarDmRdL0T/g/tQrCjBsu5OvHhzGlJv"
    "7kNjajTqpUoR+4M/dG/mw6wsA+sSwlDjeRG5ilug3pqIU0bmcH2Siaz0pXjWXAxbb2MIPK2EgYkT"
    "hG0/op9rM/g2vIO6+Tx8+PgB+/mVcFO7F/2DpnBtvo4NHcKw/FoBpxlciMj7EfL118ioNgArBQ7Q"
    "Jw0HBPcrkeCRWfjv98WvZFI6yGT0JtN+26ukNnYC4zMihAcDabruHYKYIpRCrxfKIvaNP6VN2w7b"
    "8vtUaRmJg1Nl4OqfgN6N7mjaGYy7xb7obo5C2RZlJJpnoJt2QEc+Bz7R3/Lp+0q8TlJGKF869vit"
    "h8Pcqwg8G4yf9BMw+ZvtVy+qRXlaAQw6unD6SBGilt3BoEUsNpW9hdu3vH92aSd+6U3BnPw6tOrH"
    "wLCkHloDdVBf3IzH44qRL9yGdK8S9Pk34ZcxXrhgVYBPAsFwNa+D+Jbt8P0YghCRathalkAyshpv"
    "NXPAdFdhzZYcyOYW4WtDNgZuHwHjdhxhWwnrnkTgRrQlDmbug/FoXfT1tdP/tNk/Q7e2bWfkX2+j"
    "bclHyWdFFIWWFVB8zmk67DEaO0+ma9/IWA4Z2U5ml6IoxzeaqsZYnOiiu8lwH3bvtdDlXzoGQQ7P"
    "KT1EFMFSm6jdZy2q3EbD09YMcU2j4XI1nUJi3PGS1x9z9srDxP0Gzazgwfw7Quj30sWj86r0MH0M"
    "1ocsoqzGLNrXWkTcr03xpb+ERIP90VC0HKprnbF+3BSMdQyCq34gHk9yxlDQt/h464wtd6zgkm2M"
    "pJvieCtphhv7RfEyexe8uCdi+n1pUKIrCc/vYZRLMujDc21yUGghZfMeepq8AbKiwdjPF4KRKRH4"
    "HJGFvG95xu/rAAK/1RCFgkM4J/oLihOEWS0bQVbl43i2qY6Ltd8rxN6J5WfVDo5iZ4QKsB4PH6Ox"
    "qQNf2lox2e0kpl9PxrEbHQi8VAN7k3w0OdUy/oNqpGtgiQ/1cmg5fRnNfalYwmZDX6PoD3j/GOeH"
    "0Ff9GP5FERe/YcMmLw5dEZ4oKOWDwiw9fLiqjDOG33JcRx89yR8Fle5HjMP5lfA4I43qAgmcbBwL"
    "vxo7WtR0T1chfy1ZjpgyLjwT6Z1AOfNXvp/WZ03XXgQyyTvVYVUbwYzo9dMtaZYeSQT+CVNOrbI6"
    "GnVDpNzQzxl7Njke92aNZ78Ym9GUyb7wvZyFTa7dnH1mmniTc2g0p6+UK8/ETANnzrSDgcQd3oJo"
    "k1wYWYegyYjlyMxz7ab2Nhs0ixnojmiKQK8slz6ZnGIutqqjPIxFf2scR+7dAWFmuvgHpme3Es14"
    "+5hOP3P/fi5rNRHIjcSRTdcFevN1JWNQGUOvquSYBTvEaeCT2He5Q43TOTZftaqSw8tQHPd9TMpk"
    "tu7v/Sav+/S+VIgSo5sY7SJh5Nx8w1xUGPUnO6b9tPk7T6Gg6rvdJlbHMfpr7+q0JF/VkREa4shE"
    "ikRx2hk1i2kRMw/zext1/5XY/XcST57VH3yeFfzsT7oVLt5Ea+ZvowKLT2QtpICHLaF03UWUuvb/"
    "5seWzkk0qJpPAb08nLUCm8OpKC+UxoVK4cMKQ8TzVdMms1VUE9XJVFfdJNPNW3EvIxAK57+Sxg1J"
    "yHoZg61Lx1ZXL7R1h0ILSrh1O5MyB7PpsbsOnJx+omKHYabv4nVG9UUlUzyUT1nrFSHRoYRFB60R"
    "aCqHJx8GadqsBVipZ4/rglMw+EoGLg/HYEnbbLjx6KBY0xDyxnK4vbGCAqpnUU2ZNnXKP6fqok7a"
    "Mfo+cSelkP9IMy10/ELVTvqwsVsMLktgqEEVba9VEOE9F92O3phyzwqZG9fAyfEJXcoQxaiyBRDJ"
    "mY/YACHI6A1QWp8emdXvJ22+FxSceJ52XpkIOwdJ3OZagnmiarAWt8NLGQnody+FvMorevkqgw7v"
    "6aNi//EYsayiN/lZxHMnkhI0TtOorUqkaeZHJkNqdJuCqORlCLNEKJ8e3T5Hr5YrQkRxmNpX8EF2"
    "1TOSj9OC1CE1jKiux6P857Q57iKdemtII9Yd1CufTaEF94hHpofpqEghj7pu6s4boFQnEbznmwKj"
    "+bV0/95z+nn9IFW0KEOryRyxCmqIXDoB8x6vwe4zYrDzUcPby7KQlBVC7PMSqtxxllRbJMn6TAkt"
    "4i+nzu779On8ckJ2InWndNAqFQ2E+iggW1UCumXjcC+rnvxnCSLVXhxKGka418wPv+kPSD2rlhb0"
    "TMTJLlHEv+ins2LZdNlegTI1denjxhR6KSqIDdYzUHDyOokIVJNXbSJN6bxKKdsGSevREizvSKHO"
    "siDm8jA/9aQEkEpXOTkOBJDW5gYONk2L5DmYbL318g8xLFBJlFYaxvh6ZzIOJ14yVdvTmCjvBGKU"
    "11COxCiMPVbMHONP5czNmH+atA20yPTxb7nDNKiFueWQxOxTu8FcbQ+jkI4AusrrpH1hlwfn3Zse"
    "f+kv866tyC0tG9/K/zOx/zf9/yXZCjtirE7SE5vtWPpUGr3tHRSWHkQ67AlqmCADrnHSkHUNhrbN"
    "MHVLO+POpzwyuZIAhQ2RmJhM0LnHg4Q9ycxPgytRXiEBlydFUNqxHAvPH8HTxBhorXyCDJ1a5L/v"
    "hHRQN7gb4nF+QxRuTYrC7dZyOthUSDPPeGKKTgKUd/vBwncbdLVScfSXQOxjX2BgIBfO396L5xKr"
    "oK7VgFn7JrBe1k1Ysy8cmYeeghQOY/e4aohp9iHF9hTuxh7Dg0unSaDlK7GyP9L4IVfck0nA2h95"
    "2aeffoKz9Hg2yV6FbfKexioIirDZy95gbkIpBF6HwGttHcLfDaKl+AVy3UPhVRqL7PSjSEYUeHtn"
    "shPip7OM0SIYL3eHtiMfG+rSi9kexbA/kQO/6FUw+DIHl+8vxfu3Q8z0KhVOfH+5Nhp0p16zpUiU"
    "tA5PYKcl52N9Nr8Or7Qlu+lVBFsSdoxTj7x20SIu9aecvkeAN91sWYbgI5PoiNg69nEvH7vxlhwb"
    "zL2XDdiZh6aOX9DQKcn5r7gluZ758nQ1BOTMYbxLA5J7rMCboMNZZ2pfEtRTT8NjQyawygapu32p"
    "fvtc/BUOYu8eZeb/HMuYL51EbgtkODJrXpfS/nnadGJjAMb3msA6vJYpiHzI/KuYM55lwY6Tc2Ol"
    "b+v/QZeXFyzorjkXtu+6heQ8HfY6Xy56fzajO0XRug16CuAy9GMqxptTlMMHWrxpAiIWNVJapxTD"
    "xf2aeMIC/lSzSonZUd4ebhI4cJvjCy/3BzpbR7ToSMgyKtpwjCaYZFKZhfj/6v0UnTZMsYFc7LT+"
    "raxxgDKrdv499ou8gesueRzbfBTe3LJwGWgmj9hAvGgoId8ZxgjRqIdcmS2ibNbja4IvfrSYRZ/f"
    "8aAtMRoTwrlgP+gOtv06pqtuha/dKdT0zGD3P3+KcokgSF2JgrnCCsyfeByGWd7IPOpCvUY5tOjs"
    "ELPmJC8tTfRAk1/6d/stSJEnpXA5ko/3gIFdHIf/KMoI3hHHwa9YiCrdtxhcsxI/2ISSpmgz6Vx5"
    "xjn3/Pa1DP+HhdS6yorjVyve4/TARe4Pfsk+a0s9Bn5aG88m/0Pfp1et5IxFf7jPLKywYm5sP0Ql"
    "k1wonncK47FKhflPzqG+nrNJP04Vw/17yTVVmTTsJTm29UxwZST3niLJPj3dg7mm/5QNZjmYMj7v"
    "hZm/76j/DHK/d1635I7YP6z5kvX4/qGvx9tt+hsH36jn+OR/uWa+KrYIjhcO4kDyB9ome4+U5Sdx"
    "cp2uiDTHxjqqVX/aIymkkEnn5sdpmSTM3RMPn4HL8Pm4gkyfmjHx0z1JM0kWxU8c8ZIto57uUMY4"
    "M5QC4zbjoKUgasX1ObngVUANZ93DFqOxbfZcuAb548wjExrdz4cOviwcD77CBI3fShJLBMHdFoZW"
    "6COhbirudFhy5jPhgdS8LZbJsW0jNc1rHF5unA5x73Di6K/3YTJWlx5D9mUNOunVpav47Ij235j5"
    "M53KM8NYx1po9wF7+ythHj+enT7jAPZMOgOLFZNZd7vR7OaYvai/5EHLk+I5mEhb7/pvf6t9Lpzy"
    "PaZrvjRD5Sk3O834C2b0bGKPqNiwO4s8WC2dOHZKRSKrm3yQTcgug96a8xAzMmdTp0qwPsONv93x"
    "BTtgaVCAtRXa2LLxPeyPi0PgcDTUCpdxxhdHbWXjSyPYg99KjTKPo+yKg5Es0v3ZxneebPNrF/Zz"
    "H7G/67E94DkFLOjTbfEW1smVcvteFwUrDdLszZJsi4oBqz99MltRdRrhvfJorpRkxUbvYx1GK7Ml"
    "6f4c+Ucahpx9T1x9D4lbx9l5WT2c7xC3d7CWVWMfpE5g7cc+pnUHVn2vMait5bdaJHc5G7bgHfhK"
    "w9ivnw/rSfCa6P0Xn1IDbA=="
)


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