Полное решение: Давайте заметим, что сделав операцию для какого-то конкретного числа, то мы захватим сразу все его вхождения.

Дальше заметим, что для каждого такого числа нужно как минимум 2 операции, кроме первой операции вначале, поэтому у нас получится что-то вроде 2*cnt-1,

где cnt — кол-во уникальных чисел.

Сложность: O(n).

Полное решение: Доран может ходить по диагонали, а значит Доран может захватить площадь размера 3*3, по Круга может ходить только вперед, назад, вниз и вверх. Это дает нам понять, что условие конечное, т.е в какой-то момент Доран настигнет Кругу.

Теперь определим 3 случая:

1 Когда они находятся на одной и той же строке, т.е rk==rd. В этом случае ответ зависит от позиции Круги. Если ее столбец >= столбец Дорана, то единственное место куда она может побежать — n. Поэтому ответ будет n-ck+abs(cd-ck). Иначе ответ: ck+abs(cd-ck), т.к единственное место куда она может пойти это граница 1.

2 Когда они находятся на одном и том же столбце, т.е ck==cd. Т.к n == n, ответ не сильно отличается от 1 случая, а именно: n-rk+abs(rd-rk), для первого случая, и rk+abs(rk-rd) для второго.

3 Когда оба из них не пересекаются, ни столбцом, ни строкой, и находятся в разных местах. Тут мы комбинируем условия из предыдущих случаев, а именно если столбец Дорана находится раньше, чем столбец Круги, то она побежит направо к границе n, ans1 =abs(cd-n), иначе она побежит налево, ans1 = abs(cd-0). Также и со строкой: ans2 = abs(rd-n), ans2 = abs(rd-0) для второго случая.

Выводим наш ответ.

Сложность: O(n).

Полное решение: В задаче сказано, что числа в массиве могут быть только двух видов: 0 и 1.

А значит возможные комбинации такие:

[1 1 1] [1 0 1] [1 0 0] [0 0 0] [0 1 0] [0 1 1]

Здесь можно заметить, что только в двух случаях ответ может быть 2, а именно если нет таких индексов, что a[i]==a[i+1].

Пример:

Пусть a = [1 0 1 0 1 0] . Как можем видеть у нас нет вышеупомянутых индексов, а значит к ответу добавляется 2. Можно доказать, что больше 2 не может быть.

Также второе наблюдение заключается в том, что ответ больше 1 может быть только на 1 операции, дальше неважно есть ли вышеупомянутые индексы, ответ будет не больше 1. Поэтому остается только посчитать есть ли на отрезке от l, r такие индексы, если есть хоть один такой индекс, то ответ никогда не будет больше 1, иначе это возможно. Ответ можем посчитать так: (r-l+1)/3, если есть такие индексы, иначе ответ ((r-l+1)/3-1)+2.

Стоит упомянуть, если на отрезке кол-во 0 или кол-во 1 не делится на 3, то в итоге разбиение и выполнение операции невозможно, поэтому можно сразу вывести -1.

Сложность: O(q).