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

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

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