Глобальное потепление — это важная проблема, и Джонни знает об этом. Он решил проанализировать историю температур и найти подпоследовательной дней (не обязательно последовательных), в которой температура строго возрастает. Это убедит неверующих!

Джонни нашёл исторические данные за \(n\) последовательных дней. Температура в \(i\)-й день была \(t_i\).

Формально, нам интересно найти длину наибольшей возрастающей подпоследовательности (НВП) последовательности \((t_1, t_2, \ldots, t_n)\), то есть наибольшее такое \(k\), что возможно выбрать возрастающую последовательность индексов \(1 \leq a_1 lt a_2 \lt \ldots \lt a_k \leq n\), для которой \(t_{a_1} \lt t_{a_2} \lt \ldots \lt t_{a_k}\).

Джонни хочет найти действительно длинную подпоследовательность, а поэтому он решил сжульничать. Сначала он выберет непустой отрезок дней и целое число \(d\) (\(-x \leq d \leq x\)), а затем увеличит температуру в каждый из этих дней на \(d\). Такое небольшое изменение, вероятно, не будет обнаружено обществом, но при этом оно может сделать длину НВП больше. Разрешено выбирать \(d = 0\).

Какая максимально возможная длина НВП после такого изменения?

Обратите внимание на нестандартное ограничение по памяти.

Уже долгое время вы — фанат Байтлото. Примерно столько же времени ваши родственники говорят вам, что все такие игры — это пустая трата денег. Вы уверены, что это так из-за их неумения играть! У вас есть идеальный план, и скоро все увидят, как вы выигрываете.

Есть много типов игр. Вы интересуетесь в одном из них: Битлото. Выбор был прост, так как это самый простой из предлагаемых типов игр: каждый день случайно выпадает ровно одно число. Вы записываете эти числа за \(n\) последовательных дней и получаете последовательность \(a_1, a_2, \ldots, a_n\). Вы уверены, что в этой последовательности есть какая-то закономерность, а именно, в отрезках из \(l\) последовательных дней. Ваша семья всё ещё не верит вам, так что единственный способ убедить их — это использовать серьёзную математику.

Есть \(n - l + 1\) отрезок дней длины \(l\). \(i\)-й отрезок начинается в позиции \(i\) и содержит элементы \(a_i, a_{i + 1}, \ldots, a_{i + l - 1}\). Расстояние между двумя отрезками — это количество несовпадающих элементов на соответствующих позициях. Другими словами, для отрезков \(x\) и \(y\) это количество таких \(i\) (\(0 \leq i < l\)), что \(a_{x + i}\) и \(a_{y + i}\) различны. И наконец, будем говорить, что два отрезка \(k\)-похожи, если расстояние между ними не превосходит \(k\).

Зафиксированы последовательность и число \(l\). Вам даны \(q\) запросов. В каждом запросе вам дано число \(k_j\) и для каждого из \(n - l + 1\) отрезов вы должны найти количество отрезков той же длины, которые \(k\)-похожи на данный (не считая сам этот отрезок).

Джонни основывает Bytecomp — компанию, которая предлагает вычислительные мощности в облаке. Компании этого профиля обычно обладают большим количеством быстрых компьютеров, на которых производятся вычислениях их клиентов.

Джонни ещё не купил ни одного компьютера. Он пошёл в компьютерный магазин и получил список из \(n\) доступных компьютеров. Каждый компьютер характеризуется колиеством процессорных ядер \(c_i\), частотой \(f_i\) и ценой \(v_i\). Такой компьютер имеет \(c_i\) независимых ядер, не мешающих друг другу, поэтому они могут быть назначены для выполнения разных задач.

Когда клиент делает заказ на ресурс, он определяет требуемое количество ядер \(C_j\) и минимальную необходимую частоту \(F_j\). Также заказ содержит цену \(V_j\), которую клиент собирается заплатить. Если заказ принимается, Bytecomp должна предоставить эксклюзивный доступ к вычислительным мощностям, требуемым клиентом. Джонни должен выбрать \(C_j\) ядер (возможно, из разных компьютеров), каждое частотой хотя бы \(F_j\). Эти ядра не могут быть назначены какому-нибудь другому заказу.

Помогите Джонни заработать так много денег, как это возможно: выберите оптимальное подмножество заказов для исполнения, а также подмножество компьютеров из магазина, чтобы удовлетворить все принятые заказы. Ваша цель — максимизировать итоговую прибыль, то есть разность между доходом от предоставления вычислительных ресурсов клиентам и стоимостью покупки компьютеров.