Существует массив \(a\), состоящий из \(n\) целых чисел. Изначально все элементы массива \(a\) равны \(0\).
Кевин может выполнять над массивом операции следующих двух типов:
- Прибавление на префиксе — Кевин сначала выбирает индекс \(x\) (\(1\le x\le n\)), а затем для каждого \(1\le j\le x\) увеличивает \(a_j\) на \(1\);
- Прибавление на суффиксе — Кевин сначала выбирает индекс \(x\) (\(1\le x\le n\)), а затем для каждого \(x\le j\le n\) увеличивает \(a_j\) на \(1\).
В стране KDOI люди считают, что целое число \(v\) является сбалансированным. Таким образом, Айрис даёт Кевину массив \(c\), состоящий из \(n\) целых чисел, и определяет красоту массива \(a\) следующим образом:
- Изначально \(b=0\);
- Для каждого \(1\le i\le n\), если \(a_i=v\), следует увеличить \(b\) на \(c_i\);
- Красота массива \(a\) равна конечному значению \(b\).
Кевин хочет максимизировать красоту массива \(a\) после операций. Однако он уже выполнил \(m\) операций, когда был сонным. Теперь он может выполнить произвольное количество (возможно, ноль) новых операций.
Вам нужно помочь Кевину найти максимальную возможную красоту, если он оптимально выполнит новые операции.
Однако, чтобы убедиться, что вы не просто гадаете по костям, Кевин даст вам целое число \(V\), и вам нужно будет решить задачу для каждого \(1\le v\le V\).
Выходные данные
Для каждого набора входных данных выведите \(V\) целых числа в одной строке, где \(i\)-е целое число обозначает максимальную возможную красоту после того, как Кевин выполнит некоторые новые операции, когда \(v=i\).
Примечание
В первом наборе входных данных массив \(a\) под начальными операциями изменяется следующим образом: \([0, 0, 0] \xrightarrow{\mathtt{L}\ 3} [1, 1, 1] \xrightarrow{\mathtt{R}\ 3} [1, 1, 2] \xrightarrow{\mathtt{L}\ 1} [2, 1, 2]\).
- Для \(v=1\) оптимально не выполнять никаких новых операций, и красота равна \(b=c_2=2\);
- Для \(v=2\) оптимально выполнить операцию прибавления префикса по индексу \(2\). После этого массив \(a\) становится \([3,2,2]\), и красота равна \(b=c_2+c_3=6\).
Во втором наборе входных данных для \(v=1\) и \(v=2\) оптимально не выполнять никаких новых операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 3 2
1 2 4
L 3
R 3
L 1
3 3 2
5 1 4
L 3
R 3
L 1
5 4 5
1 1 1 1 1
L 3
R 2
L 5
L 4
10 12 9
10 9 8 7 6 5 4 3 2 1
L 2
L 4
R 4
R 4
L 6
R 8
L 3
L 2
R 1
R 10
L 8
L 1
1 1 4
1000000000
L 1
|
2 6
1 9
0 1 3 5 5
0 0 0 6 25 32 35 44 51
1000000000 1000000000 1000000000 1000000000
|