Рик и Морти очень любят ходить на горный хребет Высокоорный для того, чтобы поорать — эхо там просто невероятное. Не так давно они нашли интересное акустическое свойство этого хребта: если Рик и Морти начнут одновременно орать с разных гор, то их ор будет слышен между этими горами вплоть до высоты, равной побитовому ИЛИ высот гор, на которые они взошли, и всех гор между ними.
Побитовое ИЛИ — это бинарная операция, которая определяется следующим образом. Рассмотрим записи чисел x и y в двоичной системе счисления (возможно с ведущими нулями) x = xk... x1x0 и y = yk... y1y0. Тогда z = x | y определяется следующим образом: z = zk... z1z0, где zi = 1, если xi = 1 или yi = 1, иначе zi = 0. Иными словами, нули в побитовом ИЛИ чисел находятся только в тех разрядах, в которых у обоих чисел находятся нули. Например, побитовое ИЛИ чисел 10 = 10102 и 9 = 10012 равняется 11 = 10112. В языках программирования C/C++/Java/Python данная операция обозначается как «|», а в Pascal как «or».
Помогите Рику и Морти посчитать, сколькими способами они могут выбрать две различные горы так, что если они начнут орать с этих гор, ор их будет слышен выше этих гор и всех гор между ними. Формально говоря, требуется вычислить, сколько существует таких пар l и r (1 ≤ l < r ≤ n), что побитовое ИЛИ всех высот гор на отрезке от l до r включительно строго больше высоты любой горы на этом отрезке.
Примечание
В первом примере все искомые способы — это пары гор со следующими номерами (горы нумеруются с единицы):
(1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)Во втором примере искомых пар не существует, поскольку для любой пары гор высота ора с них равна 3, и эта высота равна высоте любой из гор, следовательно она не выше их.