Из сортировки (Платина)
Беси сделала гибрид из двух любимых алгоритмов пузырьковой сортировки и быстрой сортировки:Назовём позицию между элементами i и i + 1 массива A точкой разбиения если максимум из A[...i] не больше чем минимум A[i + 1...]. Беси помнит, что быстрая сортировка реорганизует массив так, чтобы у него появилась точка разбиения, а затем рекурсивно сортирует две стороны A[...i] и A[i + 1...]. Однако хотя она помнит, что все точки разбиения можно найти за линейное время, она забыла как в быстрой сортировке реорганизуется массив, чтобы быстро создать точку разбиения. Она решила использовать пузырьковую сортировку для решения этой задачи
Ниже приведен алгоритм Беси Сначала она написала простую функцию, которая делает один проход пузырьковой сортировки:
bubble_sort_pass (A) {
for i = 0 to length(A)-2
if A[i] > A[i+1], swap A[i] and A[i+1]
}Рекурсивный код Беси для "быстрой" сортировки такой:
quickish_sort (A) {
if length(A) = 1, return
do { // Main loop
work_counter = work_counter + length(A)
bubble_sort_pass(A)
} while (no partition points exist in A)
divide A at all partition points; recursively quickish_sort each piece
}Теперь Беси интересно, насколько быстро работает её код. Для простоты она считает, что её итерация работает линейно и поэтому она просто инкрементирует глобальную переменную work_counter внутри цикла текущим размером массива так, чтобы оценивать общую работу, выполненную алгоритмом.
По заданному входному массиву, предскажите финальное значение величины work_counter после завершения алгоритма quickish_sort.
Входные данные
Первая строка содержит n (1 ≤ n ≤ 10^5). Следующие n строк описывают A[0]..A[n−1], каждый из которых является целым числом в интервале 0..10^9. Не гарантируется, что все элементы различны.
Выходные данные
Выведите конечное значение величины work_counter.
Пример
В этом примере мы начинаем с массива 20 2 3 4 9 8 7. После одного прохода пузырьковой сортировки (прибавляя 7 к work counter) мы получим массив 2 | 3 | 4 | 9 8 7 | 20 где символ | обозначает точку разбиения. Поэтому наша задача разбивается на рекурсивные подзадачи сортировки чисел 2, 3, 4, 20 (каждая занимает 0 единиц работы) и 9 8 7. Для подзадачи 9 8 7 один проход главного цикла (3 единицы работы) строит массив 8 7 | 9, после которого делается финальный вызов 8 7 (2 единицы работы) и алгоритм завершён.