У Ntarsis есть массив \(a\) длины \(n\).
Мощность подотрезка \(a_l \dots a_r\) (\(1 \leq l \leq r \leq n\)) определяется следующим образом:
- Наибольшее значение \(x\), такое что \(a_l \dots a_r\) содержит \(x\), и ни \(a_1 \dots a_{l-1}\), ни \(a_{r+1} \dots a_n\) не содержат \(x\).
- Если такого \(x\) не существует, мощность равна \(0\).
Массив \(b\) называется соперником для \(a\), если выполняются следующие условия:
- Длина и \(a\), и \(b\) равна \(n\).
- Для всех \(l, r\), где \(1 \leq l \leq r \leq n\), мощность \(a_l \dots a_r\) равна мощности \(b_l \dots b_r\).
- Элементы \(b\) являются положительными числами.
Ntarsis хочет найти соперника \(b\) для \(a\) такого, что сумма \(b_i\) (\(1 \leq i \leq n\)) будет максимальной. Помогите ему с этой задачей!
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел \(b_1, b_2, \ldots, b_n\) — допустимого соперника для \(a\) такого, что сумма \(b_1 + b_2 + \cdots + b_n\) будет максимальной.
Если существует несколько соперников с максимальной суммой, выведите любого из них.
Примечание
Для первого набора одним из соперников с максимальной суммой является \([2, 4, 2, 3, 3]\).
Можно показать, что \([2, 4, 2, 3, 3]\) является соперником для \([1, 4, 1, 3, 3]\).
Ниже перечислены все возможные подмассивы \(a\) и \(b\) и их соответствующие мощности:
- Мощность \(a[1:1] = [1] = 0\), мощность \(b[1:1] = [2] = 0\).
- Мощность \(a[1:2] = [1, 4] = 4\), мощность \(b[1:2] = [2, 4] = 4\).
- Мощность \(a[1:3] = [1, 4, 1] = 4\), мощность \(b[1:3] = [2, 4, 2] = 4\).
- Мощность \(a[1:4] = [1, 4, 1, 3] = 4\), мощность \(b[1:4] = [2, 4, 2, 3] = 4\).
- Мощность \(a[1:5] = [1, 4, 1, 3, 3] = 4\), мощность \(b[1:5] = [2, 4, 2, 3, 3] = 4\).
- Мощность \(a[2:2] = [4] = 4\), мощность \(b[2:2] = [4] = 4\).
- Мощность \(a[2:3] = [4, 1] = 4\), мощность \(b[2:3] = [4, 2] = 4\).
- Мощность \(a[2:4] = [4, 1, 3] = 4\), мощность \(b[2:4] = [4, 2, 3] = 4\).
- Мощность \(a[2:5] = [4, 1, 3, 3] = 4\), мощность \(b[2:5] = [4, 2, 3, 3] = 4\).
- Мощность \(a[3:3] = [1] = 0\), мощность \(b[3:3] = [2] = 0\).
- Мощность \(a[3:4] = [1, 3] = 0\), мощность \(b[3:4] = [2, 3] = 0\).
- Мощность \(a[3:5] = [1, 3, 3] = 3\), мощность \(b[3:5] = [2, 3, 3] = 3\).
- Мощность \(a[4:4] = [3] = 0\), мощность \(b[4:4] = [3] = 0\).
- Мощность \(a[4:5] = [3, 3] = 3\), мощность \(b[4:5] = [3, 3] = 3\).
- Мощность \(a[5:5] = [3] = 0\), мощность \(b[5:5] = [3] = 0\).
Можно показать, что не существует соперника с большей суммой, чем \(2 + 4 + 2 + 3 + 3 = 14\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
5
1 4 1 3 3
5
1 4 1 8 8
5
2 1 1 1 2
8
3 2 3 5 2 2 5 3
8
1 1 1 1 4 3 3 3
10
1 9 5 9 8 1 5 8 9 1
16
1 1 1 1 5 5 5 5 9 9 9 9 7 7 7 7
|
2 4 2 3 3
3 4 3 8 8
2 1 2 1 2
4 2 4 5 5 2 5 4
1 2 2 1 4 3 2 3
7 9 5 9 8 9 5 8 9 7
1 8 8 1 5 8 8 5 9 9 9 9 7 8 8 7
|