Дана квадратная матрица, состоящая из \(n\) строк и \(n\) столбцов ячеек, оба пронумерованы от \(1\) до \(n\). Ячейки раскрашены в белый или черный цвет. Ячейки с \(1\) до \(a_i\) черные, а ячейки с \(a_i+1\) до \(n\) белые, в \(i\)-м столбце.
Вы хотите разместить \(m\) целых чисел в матрице, от \(1\) до \(m\). Есть два правила:
- в каждой клетке должно быть не больше одного числа;
- в черных клетках не должно быть чисел.
Красота матрицы — это количество таких \(j\), что \(j+1\) написано в той же строке, в следующем столбце от \(j\) (в соседней справа ячейке).
Чему равна максимальная красота матрицы?
Выходные данные
На каждый набор входных данных выведите одно целое число — максимальную красоту матрицы после того, как вы разместите в ней все \(m\) целых чисел. Обратите внимание, что дается не больше чисел, чем белых клеток в матрице, так что ответ всегда существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
0 0 0
9
4
2 0 3 1
5
4
2 0 3 1
6
4
2 0 3 1
10
10
0 2 2 1 5 10 3 4 1 1
20
1
1
0
|
6
3
4
4
16
0
|