Задание D. Найди две единицыОграничение по времени: 0. 5 секундОграничение по памяти: 256 мегабайтПри записи чисел в фибоначчиевой системе счисления в качестве цифр используются только 0и 1. Будем использовать ноль в записи, если очередное число из последовательности Фибоначчи(1, 2, 3, 5, 8, 13, 21, . . . ) не используется, и единицу — для тех что используются. Тогда, например,17 = 13 + 3 + 1 = 100101f ib. Для однозначности представления в такой записи не должно быть двухединиц подряд, иначе, например, 17 = 8 + 5 + 3 + 1 = 11101. Такие числа подлежат нормализации. Вам требуется в строке, которая является каким то представлением числа в фибоначчиевойсистеме, для каждой позиции, кроме последней, найти ближайшее к ней справа место, на которомстоят как минимум две единицы подряд, и выдать расстояние до него или −1, если, начиная стекущей позиции, правее двух единиц подряд нет. Например, для строки 10111001101 программадолжна выдать: «2 1 0 0 3 2 1 0 -1 -1». Причем эффективная по времени программа должна находить ответ с помощью одного цикла,без использования стандартных функций и методов, работающих за длину строки. Формат входных данныхНа вход программе подается одна строка, состоящая из символов 0 или 1, начинающаяся с 1. Длина строки N не превосходит 100 000 символов. Формат выходных данныхВыведите в строку через пробел или в столбец N − 1 число — ответ на задачу для каждой изпервых N − 1 позиций строки. Примерыстандартный ввод|||||||| стандартный вывод10111001101 ||||||| 2 1 0 0 3 2 1 0 -1 -111111 |||||| 0 0 0 0ЗамечаниеКак минимум в 40% тестов длина строки не превосходит 1000.