Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))

res = 0

for i in range(N-2):
    L1 = L[i+1:]
    for j in range(len(L1)-1):
        L2 = L1[j+1:]
        for k in range(len(L2)):
            sum = L[i] + L1[j] + L2[k]
            if (sum > 2*L[i]) & (sum > 2*L1[j]) & (sum > 2*L2[k]):
                res += 1

print(res)


### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))

v = L[:]
v.sort()

res = 0

import bisect

for i in range(N-2):
    a = v[i]
    for j in range(i+1,N-1):
        b = v[j]
        sup = a + b
        #inf = max(a-b,b-a)
        iterS = bisect.bisect_left(v,sup)
        #iterI = bisect.bisect_left(v,inf+1)
        #print(a,b,sup,inf,iterS,iterI)
        res += iterS - (j+1)

print(res)
### BUGGY CODE ###

# match matching
N, M = map(int, input().split())
ok = list(map(int, input().split()))
ok.sort()
a = [i for i in range(1, 10)]
b = [2, 5, 5, 4, 5, 6, 3, 7, 6]

data = {a[i]: b[i] for i in range(9)}

dp = [[0 for i in range(N+1)] for j in range(M+1)]

for i in range(M):
    for cnt in range(N+1):
        for j in range(M):
            num = ok[j]
            cost = data[num]
            if cnt > cost:
                P = len(str(dp[i+1][cnt-cost]))
                if dp[i + 1][cnt-cost] > 0:
                    dp[i+1][cnt] = max(dp[i+1][cnt-cost] +
                                       num*10 ** P, dp[i+1][cnt])
                else:
                    dp[i+1][cnt] = max(dp[i+1][cnt-cost], dp[i+1][cnt])
            elif cnt == cost:
                dp[i+1][cnt] = max(num, dp[i+1][cnt])
            elif cnt < cost:
                dp[i+1][cnt] = max(dp[i][cnt], dp[i+1][cnt])

ans = dp[M][N]
print(ans)

### FIXED CODE ###

matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

n, m = map(int, input().split())
alist = list(map(int, input().split()))
alist.sort(reverse=True)

dp = [-1 for _ in range(n + 1)]
dp[0] = 0
for a in alist:
    match = matches[a]
    for i in range(n - match + 1):
        if dp[i] == -1: continue
        dp[i + match] = max(dp[i + match], dp[i] * 10 + a)

print(dp[-1])
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
*a, = sorted(map(int, input().split()), reverse=True)
*b, = sorted(map(int, input().split()), reverse=True)
*c, = sorted(map(int, input().split()), reverse=True)

ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i]+b[j])
ab.sort(reverse=True)
ab = ab[:k]

abc = []
for i in range(len(ab)):
    for j in range(z):
        abc.append(ab[i]+c[j])

abc.sort(reverse=True)

for i in range(k):
    print(abc[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
*a, = sorted(map(int, input().split()), reverse=True)
*b, = sorted(map(int, input().split()), reverse=True)
*c, = sorted(map(int, input().split()), reverse=True)

ab = [a[i] + b[j] for j in range(y) for i in range(x)]
ab.sort(reverse=True)
ab = ab[:k]

abc = [ab[i] + c[j] for j in range(z) for i in range(len(ab))]

abc.sort(reverse=True)

for i in range(k):
    print(abc[i])
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline
n = int(input())
b = []
for i in range(n):
  a = int(input())
  b_append = b.append
  b_append(a)

s = set(b)
c = collections.Counter(b)
ans = 0
for i in range(len(s)):
  if c.most_common()[i][1] % 2 == 0:
    continue
  else:
    ans += 1
  if c.most_common()[i][1] == 1:
    ans += len(s)-1-i
    break
print(ans)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
a.sort()
b = []
for i in range(0,n-1,2):
  if a[i] != a[i+1]:
    b.append(a[i])
    b.append(a[i+1])
  else:
    continue
if n%2 == 1:
  b.append(a[-1])
#print(b)
ans = []
if b != []:
  ans.append(b[0])
  for j in range(1,len(b)-1,2):
    if b[j] != b[j+1]:
      ans.append(b[j])
      ans.append(b[j+1])
  if len(b)%2 == 0:
    ans.append(b[-1])
#print(ans)
if ans == []:
  print(0)
else:
  print(len(ans))
### BUGGY CODE ###

n = int(input())
L = sum([list(map(int, input().split())) for i in range(n)], [])
next = 0
for i in range(len(L)):
  if L[next] == 2:
    print(i+1)
    quit()
  next = L[next]-1
print(-1)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
cur = 1
cnt = 0
while True:
    if cur == 2:
        print(cnt)
        exit()
    elif cnt > n:
        print(-1)
        exit()
    else:
        cur = a[cur - 1]
        cnt += 1
### BUGGY CODE ###

from collections import Counter
from fractions import Fraction
MOD = 10 ** 9 + 7
N = int(input())
ct = Counter()
Azero = 0
Bzero = 0
Allzero = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        Allzero += 1
    elif a == 0:
        Azero += 1
    elif b == 0:
        Bzero += 1
    else:
        f = Fraction(a, b)
        ct[f] += 1
ans = pow(2, Azero, MOD) + pow(2, Bzero, MOD) - 1
ans %= MOD
visited = set()
for f in ct.keys():
    if f in visited:
        continue
    inv = Fraction(-f.denominator, f.numerator)
    visited.add(f)
    visited.add(inv)
    tmp = pow(2, ct[f], MOD) + pow(2, ct[inv], MOD) - 1
    ans *= tmp
    ans %= MOD
ans += Allzero
print((ans-1) % MOD)


### FIXED CODE ###

from collections import Counter
from fractions import Fraction
MOD = 10 ** 9 + 7
N = int(input())
ct = Counter()
Azero = 0
Bzero = 0
Allzero = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        Allzero += 1
    elif a == 0:
        Azero += 1
    elif b == 0:
        Bzero += 1
    else:
        f = Fraction(a, b)
        ct[(f.numerator, f.denominator)] += 1
ans = pow(2, Azero, MOD) + pow(2, Bzero, MOD) - 1
ans %= MOD
visited = set()
for (a, b) in ct.keys():
    if (a, b) in visited:
        continue
    inv = Fraction(-b, a)
    ia, ib = inv.numerator, inv.denominator
    visited.add((a, b))
    visited.add((ia, ib))
    tmp = pow(2, ct[(a, b)], MOD) + pow(2, ct[(ia, ib)], MOD) - 1
    ans *= tmp
    ans %= MOD
ans += Allzero
print((ans-1) % MOD)
### BUGGY CODE ###

import sys
from collections import defaultdict
from functools import lru_cache

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7
P = 2 ** 61 - 1

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

@lru_cache(None)
def inv_mod(a):
    b = P
    u, v = 1, 0
    while a:
        t = b // a
        a, b = b - t * a, a
        u, v = v - t * u, u
    if b < 0:
        v = -v
    return v % P

def to_key(a, b):
    if a == 0:
        return -1
    x = inv_mod(a) * b % P
    return x

def pair_key(key):
    if key == -1:
        return 0
    if key == 0:
        return -1
    return P - inv_mod(key)
  
counter = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    key = to_key(a, b)
    counter[key] += 1

answer = origin
k = 1
for key, cnt in counter.items():
    key1 = pair_key(key)
    if key1 not in counter:
        k *= pow(2, cnt, MOD)
    elif key < key1:
        x, y = cnt, counter[key1]
        k *= pow(2, x, MOD) + pow(2, y, MOD) - 1
    k %= MOD
answer += k - 1
answer %= MOD
print(answer)


### FIXED CODE ###

import sys
from collections import defaultdict
from math import gcd

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

def to_standard_form(a, b):
    if a == 0:
        return (0, 1)
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        return (-a, -b)
    return (a, b)

counter0 = defaultdict(int)
counter1 = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    a, b = to_standard_form(a, b)
    if b <= 0:
        counter0[(a, b)] += 1
    else:
        counter1[(b, -a)] += 1
        counter0[(b, -a)] += 0

answer = origin
k = 1
for key, cnt0 in counter0.items():
    cnt1 = counter1[key]
    x = pow2[cnt0] + pow2[cnt1]
    k = k * (x - 1) % MOD

answer += k - 1
answer %= MOD
print(answer)
### BUGGY CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    a = na()

    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    for d in range(1, n + 1):
        for l in range(n - d + 1):
            r = l + d

            # second
            if (n - d) % 2:
                dp[l][r] = min(dp[l + 1][r] - a[l], dp[l][r - 1] - a[r - 1])

            # first
            else:
                dp[l][r] = max(dp[l + 1][r] + a[l], dp[l][r - 1] + a[r - 1])

    print(dp[0][n])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    a = na()

    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    for d in range(1, n + 1):
        for l in range(n - d + 1):
            r = l + d

            # second
            if (n - d) % 2:
                dp[l][r] = min(dp[l + 1][r] - a[l], dp[l][r - 1] - a[r - 1])

            # first
            else:
                dp[l][r] = max(dp[l + 1][r] + a[l], dp[l][r - 1] + a[r - 1])

    print(dp[0][n])


if __name__ == '__main__':
    main()
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    que = list(input().split())
    if que[0] == "1":
        s = s[::-1]
    else:
        if que[1]=="1":
            s = que[2]+s
        else:
            s = s+que[2]
print(s)

### FIXED CODE ###

from collections import deque
s = deque(list(input()))
q = int(input())
que = [list(input().split()) for _ in range(q)]
counter = 0
for i in que:
    if i[0] == "1":
        counter += 1
    else:
        if (counter+int(i[1]))%2==1:
            s.appendleft(i[-1])
        else:
            s.append(i[-1])
if counter%2==0:
    print("".join(list(s)))
else:
    print("".join(list(s)[::-1]))
### BUGGY CODE ###

import collections

num_of_numbers = int(input())
numbers = list(map(int, input().split()))
num_of_operation = int(input())

# intで初期化するため0が返る
cnt = collections.defaultdict(int)
# numbersに含まれる各数字の出現回数を保持
for i in set(numbers):
    cnt[i] = numbers.count(i)
# 初期状態の和を算出
ans = sum(numbers)

for i in range(num_of_operation):
    B, C = map(int, input().split())

    # 置換対象の数字が存在する場合
    if B in cnt:
        tmpB = cnt[B]
        tmpC = cnt[C]
        ans = ans - (B * tmpB) + (C * tmpB)

        cnt[C] = tmpC + tmpB
        cnt[B] = 0

    print(ans)




### FIXED CODE ###

import collections

num_of_numbers = int(input())
numbers = list(map(int, input().split()))
num_of_operation = int(input())

# intで初期化するため0が返る
cnt = collections.defaultdict(int)
# numbersに含まれる各数字の出現回数を保持
for i in numbers:
    cnt[i] += 1

# 初期状態の和を算出
ans = sum(numbers)

for i in range(num_of_operation):
    B, C = map(int, input().split())

    # 置換対象の数字が存在する場合
    if B in cnt:
        tmpB = cnt[B]
        tmpC = cnt[C]
        ans = ans - (B * tmpB) + (C * tmpB)

        cnt[C] = tmpC + tmpB
        cnt.pop(B)

    print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
if m!=0:
    ls = [int(input()) for _ in range(m)]

else:
    ls = []

dp = [0 for _ in range(n+1)]
dp[0]=1

if 1 in ls:
    dp[1]= 0
else:
    dp[1]= 1

for i in range(2,n+1):
    if i in ls :
        dp[i] = 0
    else:
        dp[i] = dp[i-1]+dp[i-2]
        
print(dp[n]%(10**9+7))

### FIXED CODE ###

n,m = map(int,input().split())
ls = set()
for i in range(m):
    ls.add(int(input()))
dp = [0]*(n+1)
dp[0]=1
if 1 in ls:
    dp[1]= 0
else:
    dp[1]= 1
for i in range(2,n+1):
    if i in ls :
        continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[n]%(10**9+7))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int, input().split()))

logk = k.bit_length()
doubling = []
for _ in range(logk):
  tmp = [0] * n
  doubling.append(tmp)

for i in range(n):
  doubling[0][i] = a[i] - 1

for i in range(1,logk):
  for j in range(n):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]

now = 0
pos = 0
while k:
  if k & 1:
    now = doubling[pos][now]
  k = k >> 1
  pos += 1

print(now+1)


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))

visited = [-1]*(n+1)
pos = 1
visited[pos] = 0
loop = 0
root=[1]
for i in range(1,n+1):
  pos = a[pos-1]
  if visited[pos] == -1:
    visited[pos] = i
    root.append(pos)
  else:
    loop = i - visited[pos]
    mae = visited[pos]
    break
if k < mae:
  print(root[k])
else:
  index=(k-mae)%loop
  print(root[index+mae])
### BUGGY CODE ###

import copy

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))


for _ in range(K):
    T = [0]*N
    for i in range(N):
        for j in range(max(0,i-A[i]), min(N-1, i+A[i])+1):
            T[j] += 1
    A = copy.copy(T);
    
print(*A)


### FIXED CODE ###

#pypy
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

#累積和
for _ in range(K):
    B = [0]*N
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1, i+A[i])
        B[l] += 1
        if r+1 < N: B[r+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    B, A = A, B
    if min(A) == N:
        break

print(*A)
### BUGGY CODE ###

N = int(input())
S = [[] for _ in range(N)]
count = 0
for i in range(N):
    S[i] = list(input())
    S[i].sort()
for i in range(N-1):
    for j in range(i+1,N):
        if S[i] == S[j]:
            count+=1
print(count)

### FIXED CODE ###

from math import factorial
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


N = int(input())
D = {}
L = [[]for _ in range(N)]
count = 0
for i in range(N):
    L[i] = list(input())
    L[i].sort()
    L[i] = tuple(L[i])
    if L[i] in D:
        D[L[i]] = D[L[i]] + 1
        if D[L[i]] == 2:
            D[L[i]] = D[L[i]] + 1
    else:
        D[L[i]] = 0
for key in D:
    if D[key] > 2:
        count += cmb(D[key],2)
    else:
        count += D[key]

print(count)
### BUGGY CODE ###

#C
import copy
n = int(input())
a = [int(input()) for _ in range(n)]
for i in range(n):
    tmp = copy.copy(a)
    tmp.pop(i)
    print(max(tmp))

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
max_a = max(a)
max_idx = a.index(max_a)
for i in range(n):
    if i == max_idx:
        tmp = a
        tmp.sort(reverse=True)
        print(tmp[1])
    else:
        print(max_a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {0: n * d}

    def dfs(m, cost):
        if m not in memo or memo[m] > cost:
            memo[m] = cost
            memo[0] = min(memo[0], cost + m * d)

            if m > 0:
                dfs(m // 2, cost + (m % 2) * d + a)
                dfs(m // 3, cost + (m % 3) * d + b)
                dfs(m // 5, cost + (m % 5) * d + c)

                dfs((m + (2 - m % 2) % 2) // 2, cost + (2 - m % 2) % 2 * d + a)
                dfs((m + (3 - m % 3) % 3) // 3, cost + (3 - m % 3) % 3 * d + b)
                dfs((m + (5 - m % 5) % 5) // 5, cost + (5 - m % 5) % 5 * d + c)

    dfs(n, 0)
    print(memo[0])


### FIXED CODE ###

import sys
from heapq import heappush, heappop
from collections import defaultdict, deque
sys.setrecursionlimit(10**9)


def solve(n, a, b, c, d):
    MAX = n * max(a, b, c, d) + 1
    memo = defaultdict(lambda: MAX)

    def dfs(m, cost):
        if memo[m] <= cost:
            return
        memo[m] = cost

        if m > 0:
            dfs(m // 2, cost + (m % 2) * d + a)
            dfs(m // 3, cost + (m % 3) * d + b)
            dfs(m // 5, cost + (m % 5) * d + c)

            dfs((m + (2 - m % 2)) // 2, cost + (2 - m % 2) * d + a)
            dfs((m + (3 - m % 3)) // 3, cost + (3 - m % 3) * d + b)
            dfs((m + (5 - m % 5)) // 5, cost + (5 - m % 5) * d + c)

            dfs(0, cost + m * d)

    dfs(n, 0)
    return memo[0]


t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    ans = solve(n, a, b, c, d)
    print(ans)
### BUGGY CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N,M = [int(x) for x in input().split()]
idls =[]
for i in range(N):
    idls.append(i+1)
ans =[]
for i in range (M):
    L,R = [int(x) for x in input().split()]
    iidls = set(idls[L-1:R])
    ans.append( iidls)


s = ans[0]
for i in range(M-1):
    s1 = s.intersection(ans[i+1])
    s = s1

print(len(s))







### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N,M = [int(x) for x in input().split()]
Llist =[]
Rlist =[]
for i in range (M):
    L,R = [int(x) for x in input().split()]
    Llist.append(L)
    Rlist.append(R)
 
lmax = max(Llist)
Rmax = min(Rlist)

if lmax > Rmax:
    print(0)
else:
    print(Rmax-lmax+1)
### BUGGY CODE ###

from collections import Counter
S = input()
MOD = 10 ** 9 + 7
ans = 0
front = [0, 0, 0, 0]
back = [0, 0, 0, 0]
m = { 'A': 0, 'B': 1, 'C': 2, '?': 3 }
for c in S:
  back[m[c]] += 1

pow3 = [1]
for i in range(max(3, back[3])):
  pow3.append(pow3[-1] * 3)

for i in range(len(S)):
  c = S[i]
  back[m[c]] -= 1
  # Bの位置を固定
  if c == 'B' or c == '?':
    fbsum = front[3] + back[3]
    # ?を使わない
    ans += front[0] * back[2] * (pow3[fbsum])
    # Aだけ?をつかう
    ans += front[3] * back[2] * (pow3[fbsum - 1])
    # Cだけ?をつかう
    ans += front[0] * back[3] * (pow3[fbsum - 1])
    # 両方?をつかう
    ans += front[3] * back[3] * (pow3[fbsum - 2])
    ans %= MOD
  front[m[c]] += 1

print(int(ans))

### FIXED CODE ###

from collections import Counter
S = input()
MOD = 10 ** 9 + 7
ans = 0
front = [0, 0, 0, 0]
back = [0, 0, 0, 0]
m = { 'A': 0, 'B': 1, 'C': 2, '?': 3 }
for c in S:
  back[m[c]] += 1

pow3 = [1]
for i in range(max(3, back[3])):
  pow3.append((pow3[-1] * 3) % MOD)

for i in range(len(S)):
  c = S[i]
  back[m[c]] -= 1
  # Bの位置を固定
  if c == 'B' or c == '?':
    fbsum = front[3] + back[3]
    # ?を使わない
    ans += front[0] * back[2] * (pow3[fbsum])
    # Aだけ?をつかう
    ans += front[3] * back[2] * (pow3[fbsum - 1])
    # Cだけ?をつかう
    ans += front[0] * back[3] * (pow3[fbsum - 1])
    # 両方?をつかう
    ans += front[3] * back[3] * (pow3[fbsum - 2])
    ans %= MOD
  front[m[c]] += 1

print(int(ans))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
INF = 1<<32


from bisect import bisect_left, bisect_right

def solve(N: int, M: int, A: "List[int]"):
        
    def binary_search(left: int, right: int):
        s = 0
        c = 0
        mi = INF

        while right-left > 1 or c < M:
            # print("test: ", left, " ", right)
            mid = (left+right)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            # s = []
            s = 0
            c = 0
            mi = INF
            for i in range(N):
                p = bisect_left(A, mid-A[i])
                if len(A[p:]) > 0:
                    mi = min(mi, A[i]+A[p])
                # print(A[i], A[p:], aq[N]-aq[p],  A[i]*(N-p))
                s += aq[N]-aq[p]
                s += A[i]*(N-p)
                c += N-p
                
            # mid以上の握手の個数がM以上か否か
            if c > M:
                left = mid

            else:
                right = mid
        
        s -= (c-M)*mi

        return s

    A.sort()
    aq = [0] * (N+1)
    for i in range(N):
        aq[i+1] = aq[i] + A[i]

    print(binary_search(1, A[-1]*2))
    
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
INF = 1<<32


from bisect import bisect_left, bisect_right

def solve(N: int, M: int, A: "List[int]"):
        
    def binary_search(left: int, right: int):
        s = 0
        c = 0
        mi = INF

        while right-left > 1 or c < M:
            # print("test: ", left, " ", right)
            mid = (left+right)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            # s = []
            s = 0
            c = 0
            mi = INF
            for i in range(N):
                p = bisect_left(A, mid-A[i])
                if p != N:
                    mi = min(mi, A[i]+A[p])
                # print(A[i], A[p:], aq[N]-aq[p],  A[i]*(N-p))
                s += aq[N]-aq[p]
                s += A[i]*(N-p)
                c += N-p
                
            # mid以上の握手の個数がM以上か否か
            if c > M:
                left = mid

            else:
                right = mid
        
        if c > M:
            s -= (c-M)*mi

        return s

    A.sort()
    aq = [0] * (N+1)
    for i in range(N):
        aq[i+1] = aq[i] + A[i]

    print(binary_search(1, A[-1]*2))
    
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N=int(input())
A=[int(x) for x in input().split()]
sA=[]
for i in range(N):
  b=bin(A[i])
  j=-1
  p=0
  ss=set()
  while b[j]!="b":
    if b[j]=="1":
      ss.add(p)
    p+=1
    j-=1
  sA.append(ss)
st=set()
j=-1
ans=0
for i in range(N):
  while j<N-1:
    if not st&sA[j+1]:
      st|=sA[j+1]
      j+=1
    else:
      break
  g=j-i+1
  ans+=g
  st-=sA[i]
print(ans)

### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
st=0
j=-1
ans=0
for i in range(N):
  while j<N-1:
    if not st&A[j+1]:
      st|=A[j+1]
      j+=1
    else:
      break
  g=j-i+1
  ans+=g
  st-=A[i]
print(ans)