PotentialArithmeticSequence

We have a sequence of N positive integers: a[0] through a[N-1]. You do not know these integers. All you know is the number of trailing zeros in their binary representations. You are given a int[] d with N elements. For each i, d[i] is the number of trailing zeros in the binary representation of a[i].

For example, suppose that a[0]=40. In binary, 40 is 101000 which ends in three zeros. Therefore, d[0] will be 3.

You like arithmetic sequences with difference 1. (That is, sequences in which each element is 1 greater than the previous one. For example, {4,5,6,7}.) For simplicity, we will call these sequences "incrementing sequences".

You would like to count all non-empty contiguous subsequences of the sequence a[0], a[1], ..., a[N-1] that can be incrementing sequences (given the information you have in d).

More precisely: For each pair (i,j) such that 0 <= i <= j <= N-1, we ask the following question: "Given the values d[i] through d[j], is it possible that the values a[i] through a[j] form an incrementing sequence?"

For example, suppose that d = {0,1,0,2,1}. For i=0 and j=3 the answer is positive: it is possible that the values a[0] through a[3] are {1,2,3,4} which is an incrementing sequence. For i=1 and j=4 the answer is negative: there is no incrementing sequence with these numbers of trailing zeros in binary.

Compute and return the number of contiguous subsequences of a[0], a[1], ..., a[N-1] that can be incrementing sequences.