Codeforces Round 790 (Div. 4) |
---|
Закончено |
Единственная разница между двумя версиями состоит в том, что в этой версии $$$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]$$$.
Пересечение происходит, когда два провода имеют общую точку. На картинке выше пересечения обведены красным.
Какое максимальное количество пересечений может быть при оптимальном размещении проводов?
Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.
Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \leq n \leq 1000$$$) — длина массива.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — элементы массива.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.
Для каждого набора выведите единственное целое число — максимальное количество пересечений, при оптимальном расположении проводов.
474 1 4 6 7 7 522 11132 2 2
6 1 0 3
Первый пример показан на втором рисунке в условии.
Во втором примере при единственно возможном соединении появляется пересечение двух проводов, поэтому ответ равен $$$1$$$.
В третьем тестовом примере единственно возможное соединение состоит из одного провода, поэтому ответ равен $$$0$$$.
Название |
---|