Феоктист Всеволодович — преподаватель физкультуры старой закалки, глубоко убеждённый, что в начале каждого урока школьников необходимо построить по росту. Для этого он сначала просит школьников построиться самостоятельно, после чего последовательно меняет местами произвольную пару стоящих рядом учеников, пока шеренга не примет желанный вид.
Всего на урок пришло \(N\) детей, изначально построившихся таким образом, что рост стоящего на позиции \(i\) равен \(h_i\) (используется нумерация c \(1\)). Можно считать, что все числа \(h_i\) различны и лежат в диапазоне от 1 до \(N\). Шеренга считается упорядоченной, если на первой позиции стоит школьник ростом один, на второй позиции стоит школьник ростом два и так далее.
Феоктист Всеволодович получает большое удовольствие от процесса упорядочивания школьников, поэтому он всегда выбирает наиболее длинную последовательность обменов. С другой стороны, он не хочет чтобы ученики догадались о том, что он умышленно затягивает построение, поэтому никогда не делает заведомо бессмысленных обменов. А именно, преподаватель никогда не меняет местами школьников на позициях \(i\) и \(j\), если \(h_i < h_j\) . Очевидно, что данное ограничение делает процесс сортировки шеренги по росту конечным.
Староста Саша очень любит играть в волейбол и прекрасно понимает, что чем дольше преподаватель будет расставлять всех по местам, тем меньше времени останется для игры. Ученики уже построились некоторым образом, а Феоктист Всеволодович вышел поговорить по телефону, так что Саша может успеть поменять местами ровно двух школьников, необязательно стоящих рядом в шеренге. Разумеется, он хочет сделать это таким образом, чтобы преподаватель как можно быстрее закончил упорядочивать шеренгу (Саша давно уже раскусил, как именно действует Феоктист Всеволодович). С информатикой у старосты всегда были определённые проблемы, поэтому ему требуется ваша помощь.
В первой строке ввода содержится единственное число N — количество школьников на уроке (\(1 \le N \le 1 000 000\)).
Во второй строке записано \(N\) различных целых чисел \(h_i\) (\(1 \le h_i \le N\)). \(i\)-е число соответствует росту школьника стоящего на \(i\)-й позиции
Выведите два числа — номера позиций школьников, которым необходимо поменяться местами, чтобы минимизировать количество действий преподавателя. Если таких пар несколько, то выведите любую из них. Если никому меняться местами не нужно, выведите -1 -1
В первом примере из условия после Сашиной перестановки, получится последовательность {2, 1, 3, 5, 4}, и тренер сможет сделать всего два обмена, перед тем как последовательность станет упорядоченной (например, он может поменять местами 1-го и 2-го школьника, а затем 4-го и 5-го). Если Саша поменяет местами двух других школьников, тренер затем сможет сделать три или более обменов.
Тесты к этой задаче состоят из одиннадцати групп. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
5 2 4 3 5 1
2 5
4 1 2 3 4
-1 -1
10 2 3 7 1 5 10 4 6 9 8
3 7
Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал \(a\) баллов, второй — \(b\), а третий \(c\), то говорят, что игра закончилась со счетом \(a:b:c\).
Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в \(k\) раз.
После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа \(x_1, x_2, …, x_n\). Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.
Требуется написать программу, которая по числу \(k\) и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.
Первая строка входного файла содержит два целых числа: \(n\) и \(k (3 \le n \le 100 000, 1 \le k \le 10^9\) ).
Вторая строка входного файла содержит \(n\) целых чисел \(x_1, x_2, …, x_n (1 \le x_i \le 10^9 )\).
Выходной файл должен содержать одно целое число — искомое количество различных вариантов счета.
В приведенном примере Андрей сможет показать следующие варианты счета: 1:1:2, 1:2:1, 2:1:1, 1:2:2, 2:1:2, 2:2:1, 2:2:3, 2:3:2, 3:2:2. Другие тройки чисел, которые можно составить с использованием имеющихся карточек, не удовлетворяют заданному условию, что баллы любых двух игроков различаются не более чем в \(k\) = 2 раза.
В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.
\(3 \le n \le 100 000, k = 1, 1 \le x_i \le 100 000\)
\(3 \le n \le 100, k \le 100, 1 \le x_i \le 100\)
\(3 \le n \le 100 000, k \le 10^9 \le x_i \le 10^9\), все \(x_i\) различны
\(3 \le n \le 100 000, k \le 10^9 \le x_i \le 10^9\)
5 2 1 1 2 2 3
9
Домагой смотрит на руку Мате, играя в очень упрощённую версию игры «Ханаби». Для простоты скажем, что Мате держит в руке N карт, пронумерованных числами 1, 2, ..., N в каком-то фиксированном порядке (каждое из чисел от 1 до N соответствует ровно одной карте). Как и в настоящей игре, Мате не может менять порядок карт.
Домагой указывает Мате на подотрезок последовательности карт, после чего Мате «разворачивает» этот отрезок карт.
При развороте отрезка карт меняются местами первая и последняя карты отрезка, вторая и предпоследняя и так далее. Как и все мы, Домагой — большой любитель неподвижных точек, то есть таких карт, числа на которых совпадают с номером позиции этих карт (считая слева направо со стороны Домагоя). Поэтому Домагой хочет максимизорать число неподвижных точек после поворота какого-то подотрезка.
Помогите Домагою найти такой подотрезок, после разворота которого число неподвижных точек будет максимальным.
В первой строке вводится единственное число N — число кард в руке Мате ( 1 ≤ N ≤ 5·10 5 ). Во второй строке вводятся N различных целых чисел от 1 до N — карты в руке Мате в том порядке, в котором Домагой видит их.
Выведите два числа A и B , числа на картах, являющихся началом и концом отрезка, который надо развернуть, чтобы максимизировать число неподвижных точек.
Программа, верно работающая на тестах, в которых N ≤ 500 , оценивается в 30 баллов. Программа, верно работающая на тестах, в которых N ≤ 5 000 , оценивается в 60 баллов.
4 3 2 1 4
3 1
2 1 2
1 1
7 3 6 5 7 4 1 2
6 1
Правильные скобочные последовательности определяются следующим образом:
Зная число \(n\), выведите все правильные скобочные последовательности длины \(2n\) в лексикографическом порядке. Символ '(' считается меньше символа ')'.
Единственная строка содержит одно целое число \(n\) (\(1 \le n \le 12\)).
Выведите все правильные скобочные последовательности в лексикографическом порядке.