— I want people to stop gifting each other arrays.
O_o and Another Young Boy
Массив из \(n\) целых положительных чисел \(a_1,a_2,\ldots,a_n\) упал на вас с небес вместе с целым положительным числом \(k \le n\).
Вы можете применить следующую операцию не более \(k\) раз:
- Выбрать индекс \(1 \le i \le n\) и целое число \(1 \le x \le 10^9\). Затем выполнить \(a_i := x\) (присвоить \(x\) значению \(a_i\)).
Затем вы строите полный неориентированный взвешенный граф с \(n\) вершинами, пронумерованными целыми числами от \(1\) до \(n\), где ребро \((l, r)\) (\(1 \le l < r \le n\)) имеет вес \(\min(a_{l},a_{l+1},\ldots,a_{r})\).
Вам необходимо найти максимально возможный диаметр итогового графа после применения не более \(k\) операций.
Диаметр неориентированного взвешенного графа равен \(\max\limits_{1 \le u < v \le n}{\operatorname{d}(u, v)}\), где \(\operatorname{d}(u, v)\) является длиной кратчайшего пути между вершинами \(u\) и \(v\) данного графа.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — максимально возможный диаметр итогового графа после применения не более \(k\) операций.
Примечание
В первом наборе входных данных один из оптимальных итоговых массивов — \([2,4,5]\).
Граф, полученный из данного массива:
\(\operatorname{d}(1, 2) = \operatorname{d}(1, 3) = 2\) и \(\operatorname{d}(2, 3) = 4\), поэтому диаметр графа равен \(\max(2,2,4) = 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 1
2 4 1
3 2
1 9 84
3 1
10 2 6
3 2
179 17 1000000000
2 1
5 9
2 2
4 2
|
4
168
10
1000000000
9
1000000000
|