You are given a list of n bits {x1,x2,...,xn} with each xi being an element in {0,1}. you have to output either: a) a natural number k such that xk =1 or b) 0 if all bits are equal to zero. the only operation you are allowed to access the inputs is a function I(i, j) defined as:

I(i, j) = { 1 (if some bit in xi, xi+1,...,xj has vaue 1), or 0, (if all bits xi, xi+1,...,xj have value 0}.

the function I(.,.) runs in constant time.

design a divide and conquer algorithm. describe the algorithm in words. no pseudocode. state the recurrence relation.