Сортировка Таноса является одной из сортировок, которая работает за линейное от длины массива время.

Алгоритм сортировки следующий:

1) Если массив $$$a = (a_1, \cdots , a_n)$$$ уже отсортирован, то процесс завершается. Массив считается отсортированным, если для каждого $$$i$$$ от $$$2$$$ до $$$n$$$ верно, что $$$a_{i-1} \le a_i$$$.

2) Иначе случайным образом выбираются либо первые $$$\lceil \frac{n}{2} \rceil$$$ элементов массива, либо последние $$$\lfloor \frac{n}{2} \rfloor$$$ элементов. Все они удаляются, и алгоритм переходит к шагу 1.

Например, сортировка массива $$$[10, 4, 5, 6, 8]$$$ может выглядеть следующим образом:

$$$[10, 4, 5, 6, 8]$$$ -> $$$[6, 8]$$$

Или:

$$$[10, 4, 5, 6, 8]$$$ -> $$$[10, 4, 5]$$$ -> $$$[10, 4]$$$ -> $$$[10]$$$

Поскольку при сортировке Таноса много элементов может исчезнуть, для массива $$$a$$$ определим $$$f(a)$$$ как математическое ожидание числа элементов, оставшихся в итоговом массиве.

Вам дан некоторый массив $$$a$$$.

Необходимо обработать следующие запросы:

$$$i, x$$$ – присвоить $$$a_i := x$$$.

После каждого запроса необходимо вывести $$$f(a)$$$ для текущего массива.