По условию максимальная стоимость покраски не превышает $$$100$$$. Тогда рассмотрим такую пару длин $$$len_1, len_2$$$, что $$$1 \leq len_1 < len_2 \leq n$$$ и $$$cost_{len_1} = cost_{len_2}$$$, тогда за стоимость покраски подотрезка длины $$$len_1$$$ мы можем покрасить подотрезок длины $$$len_2$$$, поэтому среди пары длин подотрезков с одинаковой стоимостью всегда выгоднее брать ту, у которой длина больше. Тогда у нас остается не более $$$100$$$ интересных длин, которые мы будем рассматривать для подсчета динамики.

Чтобы быстро проверять, есть ли хотя бы одна $$$1$$$ на отрезке $$$\left[l, r\right]$$$ в изначальном массиве, в самом начале предподсчитаем массив префиксных $$$pref_i = \sum_{j = 1}^{i}a_j$$$ и тогда на запрос проверки отрезка $$$\left[l, r\right]$$$ нужно проверить, что $$$pref_r - pref_{l - 1} > 0$$$.

Будем считать динамику $$$dp_i$$$ — минимальная сумма, за которую можно покрасить префикс длины $$$i$$$.

База: $$$dp_0 = 0$$$

Переходы выглядят следующим образом:

Пусть мы хотим пересчитать $$$dp_i$$$. Будем перебирать длину подотрезка, который мы хотим сейчас покрасить, пусть она равна $$$len$$$.

Тогда возможны два случая:

• На подотрезке $$$\left[i - len + 1, i\right]$$$ в изначальном массиве $$$a$$$ была хотя бы одна единица. Тогда мы можем за $$$cost_{len}$$$ покрасить подотрезок $$$\left[i - len + 1, i\right]$$$ и соответственно пересчитать $$$dp_i$$$ через $$$dp_{i - len} + cost$$$
• На подотрезке $$$\left[i - len + 1, i\right]$$$ в изначальном массиве $$$a$$$ не было единиц. Тогда мы должны потребовать, чтобы мы пересекались с другим подотрезком, и в пересечении находилась хотя бы одна единица. Таким образом, в данном случае $$$dp_i$$$ пересчитается через $$$dp_{i - len + 1} + cost_{len}$$$.

Так как мы рассматриваем всего $$$100$$$ длин и проверка наличия на отрезке единицы выполняется за $$$\mathcal{O}\left(1\right)$$$, то итоговая ассимптотика получается $$$\mathcal{O}\left(100 \cdot n\right)$$$ на каждый тестовый набор.