High Cry

면책 조항: 러시아어판 문제 설명에는 번역할 수 없는 말장난이 많이 있으므로, 여러분이 러시아어를 배워야 할 이유가 하나 더 있다 :)

Rick and Morty는 크게 소리치기 위해 High Cry 산맥에 가는 것을 좋아한다. 그곳에는 비범한 메아리가 있기 때문이다. 최근 그들은 이 산맥의 흥미로운 음향적 특성을 발견했다. Rick and Morty가 서로 다른 산에서 동시에 소리치기 시작하면, 그들의 외침은 그들이 오른 산들과 그 사이에 있는 모든 산의 비트 단위 OR와 같은 높이까지 이 산들 사이에서 들린다.

Bitwise OR는 다음과 같이 정의되는 이항 연산이다. 이진법으로 나타낸 수 x와 y의 표현(앞에 영이 붙을 수도 있음) x = xk... x1x0 및 y = yk... y1y0를 생각하자. 그러면 z = x | y는 다음과 같이 정의된다. z = zk... z1z0이며, xi = 1 또는 yi = 1이면 zi = 1이고, 그렇지 않으면 zi = 0이다. 다시 말해, 두 수의 비트 단위 OR에서 한 자릿값이 영일 때, 그리고 그럴 때에만 두 수의 대응하는 위치에 있는 자릿값이 모두 영이다. 예를 들어 수 10 = 10102와 9 = 10012의 비트 단위 OR는 11 = 10112이다. 프로그래밍 언어 C/C++/Java/Python에서는 이 연산을 «|»로, Pascal에서는 «or»로 정의한다.

Help Rick and Morty가 두 산을 선택하여 그 산들에서 소리치기 시작했을 때 그들의 외침이 그 산들과 그 사이에 있는 모든 산보다 높은 곳에서 들리게 되는 경우의 수를 계산하라. 더 형식적으로는, l와 r 사이(양 끝 포함)에 있는 모든 산 높이의 비트 단위 OR가 이 구간에 있는 어떤 산의 높이보다도 큰, l와 r (1 ≤ l < r ≤ n)의 쌍의 수를 구해야 한다.

첫째 줄에는 산맥에 있는 산의 수를 나타내는 정수 n (1 ≤ n ≤ 200 000)이 주어진다.

둘째 줄에는 산맥에 놓인 순서대로 산의 높이를 나타내는 n개의 정수 ai (0 ≤ ai ≤ 109)이 주어진다.

서로 다른 두 산을 고르는 경우의 수를 나타내는 유일한 정수를 출력한다.

첫 번째 테스트 케이스에서 가능한 모든 경우는 다음 번호의 산으로 이루어진 쌍이다(하나부터 번호를 매김).

(1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)

두 번째 테스트 케이스에서는 그러한 쌍이 없다. 어떤 산의 쌍을 골라도 그 산들에서 나는 외침의 높이는 3이며, 이 높이가 어떤 산의 높이와 같기 때문이다.