Оля реализовала новую для себя сортировку. На вход программа получает массив из элементов и набор значений d, расположенных от больших к меньшим. На каждом шаге алгоритма между собой сравниваются и сортируются все элементы, находящиеся друг от друга на расстоянии d, после чего берётся следующее значение для d и так продолжается до тех пор, пока d не будет равен 1 (см. пример). После этого массив будет гарантированно отсортирован.
Примечание:
Элемент A[j] находится на расстоянии d от элемента A[i ], если A[i + d] = A[j] или A[i - d] = A[j].
D – массив из элементов d
i. Алгоритм выполняется для всех из массива последовательно.
Пример работы сортировки:
для массива A = [7, 2, 4, 6] и значений D = [3, 2, 1]
d = 3: [7, 6]; [2]; [4] => [6, 7]; [2]; [4] => [6, 2, 4, 7]
d = 2: [6, 4]; [2; 7] => [4; 6]; [2; 7] => [4, 2, 6, 7]
d = 1: [4, 2, 6, 7] => [2, 4, 6, 7]
Получили [2, 4, 6, 7]
На вход программе подаётся:
Массив A = [72, 26, 114, 15, 21, 39, 6, 40, 115, 13, 7]
И значения D = [7, 3, 1]
Представим, что из-за сбоя алгоритм не закончил сортировку и остановился сразу перед значением d = 1 (выполнив сортировку для d = 7 и d = 3, но не выполнив для d = 1).
Какой элемент будет находиться в массиве по индексу “6” после этих преобразований? Индексы в массиве пронумерованы с нуля. В ответ запишите число.