Московская командная олимпиада: Московская командная олимпиада 2017, лига А

Рик и Морти очень любят ходить на горный хребет Высокоорный для того, чтобы поорать — эхо там просто невероятное. Не так давно они нашли интересное акустическое свойство этого хребта: если Рик и Морти начнут одновременно орать с разных гор, то их ор будет слышен между этими горами вплоть до высоты, равной побитовому ИЛИ высот гор, на которые они взошли, и всех гор между ними.

Побитовое ИЛИ — это бинарная операция, которая определяется следующим образом. Рассмотрим записи чисел \(x\) и \(y\) в двоичной системе счисления (возможно с ведущими нулями) \(x = x_k \dots x_1 x_0\) и \(y = y_k \dots y_1 y_0\). Тогда \(z = x\,or\,y\) определяется следующим образом: \(z = z_k \dots z_1 z_0\), где \(z_i=1\), если \(x_i=1\) или \(y_i=1\), иначе \(z_i=0\). Иными словами, нули в побитовом ИЛИ чисел находятся только в тех разрядах, в которых у обоих чисел находятся нули. Например, побитовое ИЛИ чисел \(10=1010_2\) и \(9=1001_2\) равняется \(11 = 1011_2\). В языках программирования C/C++/Java/Python данная операция обозначается как |, а в Pascal как or.

Помогите Рику и Морти посчитать, сколькими способами они могут выбрать две различные горы так, что если они начнут орать с этих гор, ор их будет слышен выше этих гор и всех гор между ними. Формально говоря, требуется вычислить, сколько существует таких пар \(l\) и \(r\) (\(1 \leq l < r \leq n\)), что побитовое ИЛИ всех высот гор на отрезке от \(l\) до \(r\) включительно строго больше высоты любой горы на этом отрезке.