Дан массив. С ним можно делать операции 1) add <element>

<index> - добавляет элемент element на позицию index
2) get <index> - возвращает значение элемента на позиции index
(Индексация с нуля, а не с единицы)
Функция добавления не заменяет элемент на индексе, а "сдвигает" другие элементы.

приведу пример.
a = [1, 2, 3, 4, 5]
>>> add 10 3
a = [1, 2, 3, 10, 4, 5]
>>> index 3
<<< 10
При самом простом решение данной задачи можно создать массив, затем при добавлении элемента
смещать элементы друг за другом. Очевидно, что сложность алгоритма при больших размерах массива
зависит от операции add, т.к. подобное присвоение занимает O(n) времени, что чрезвычайно долго.
Хотелось бы, чтобы алгоритм успевал работать для любых 2* 10^5 запросов.
Т.е. сделать добавление и получение элемента хотя бы меньше чем за O(sqrt(n)). Желательно за O(log(N))

Назову эту структуру данных "добрым массивом". Как её реализовать?

Часть 2:
Уж не уверен, что это вообще возможно, но всё же...

Space O(N)
Search O(log(N))
Insert O(log(N))
Delete O(log(N))
Iterate All O(N)
push_back O(1) <- Average
pop_back O(1) <- Average
push_front O(1) <- Average
pop_front O(1) <- Average
Sort O(N * log (N))

похоже на неявное дд

Операции, описанные в первой части, работают в среднем за лог, а вот во второй части я вообще не уверен, что все эти операции могут выполняться одновременно с такой асимптотикой. За лог их дд тоже умеет поддерживать, а за единицу вряд ли

Скиплист?