CF1609F Interesting Sections

William has an array of non-negative numbers $ a_1, a_2, \dots, a_n $ . He wants you to find out how many segments $ l \le r $ pass the check. The check is performed in the following manner: 1. The minimum and maximum numbers are found on the segment of the array starting at $ l $ and ending at $ r $ . 2. The check is considered to be passed if the binary representation of the minimum and maximum numbers have the same number of bits equal to 1.

The first line contains a single integer $ n $ ( $ 1 \le n \le 10^6 $ ), the size of array $ a $ . The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 10^{18} $ ), the contents of array $ a $ .

Output a single number — the total number of segments that passed the check.