Единственная разница между двумя версиями состоит в том, что в этой версии \(n \leq 1000\) и сумму значений \(n\) по всем наборам входных данных теста не превосходит \(1000\).
Терминал — это ряд без промежутков из \(n\) равных отрезков, пронумерованных от \(1\) до \(n\) по порядку. Есть два терминала, один над другим.
Вам дан массив \(a\) длины \(n\). Для всех \(i = 1, 2, \dots, n\) должен быть прямой провод из некоторой точки на отрезке \(i\) верхнего терминала в некоторую точку на отрезке \(a_i\) нижнего терминала. Например, на следующих рисунках показаны два возможных соединения, при \(n=7\) и \(a=[4,1,4,6,7,7,5]\).
Пересечение происходит, когда два провода имеют общую точку. На картинке выше пересечения обведены красным.
Какое максимальное количество пересечений может быть при оптимальном размещении проводов?
Примечание
Первый пример показан на втором рисунке в условии.
Во втором примере при единственно возможном соединении появляется пересечение двух проводов, поэтому ответ равен \(1\).
В третьем тестовом примере единственно возможное соединение состоит из одного провода, поэтому ответ равен \(0\).