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

n = int(input())

M = pow(10, 9) + 7
import sys

dc = {}
al = [0]

rr = [1]


def search(ss, start, end):
    z = al[(start + end)//2]
    nz = al[(start + end)//2+1]
    if z <= ss and ss < nz:
        return (start+end)//2
    elif ss < z:
        return search(ss, start, (start+end)//2)
    else:
        return search(ss, (start+end)//2+1, end)

c = 0
cn = 0
for line in sys.stdin:
    a = int(line)
    if a in dc:
        ss = dc[a]
        if ss != c-1:
            if ss >= al[cn]:
                rr.append((rr[cn]*2)%M)
            else:
                i = search(ss, 0, cn)
                rr.append((rr[cn] + rr[i])%M)
            al.append(c)
            cn += 1
    dc[a] = c
    c += 1
print(rr[cn]%M)


### FIXED CODE ###

n = int(input())

M = pow(10, 9) + 7
import sys

dc = {}
al = [0]

rr = [1]


def search(ss, start, end):
    z = al[(start + end)//2]
    nz = al[(start + end)//2+1]
    if z <= ss and ss < nz:
        return (start+end)//2
    elif ss < z:
        return search(ss, start, (start+end)//2)
    else:
        return search(ss, (start+end)//2+1, end)

c = 0
cn = 0
for line in sys.stdin:
    a = int(line)
    if a in dc:
        ss = dc[a]
        if ss != c-1:
            if ss >= al[cn]:
                rr.append((rr[cn]*2)%M)
            else:
                i = search(ss, 0, cn)
                rr.append((rr[cn] + rr[i])%M)
            al.append(c)
            cn += 1
    dc[a] = c
    c += 1
print(rr[cn]%M)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

n=int(input())
xs=input()
lxs=list(xs)
#xj=xs.count("1")
#xj=sum([1 for l in lxs if l=="1"])

xj=0
for i in range(0,n,64):
    i64=i+64
    if i64>n:i64=n
    xj+=popcount(int(xs[i:i64],2))

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    if xs[n-1-i]=="0":
        pxi=xj+1
        xi=(xip+i1%pxi)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        xi=(xim-i1%pxi)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
#        xi=xi%(bin(xi).count("1"))
        xi=xi%popcount(xi)
    print(icnt)



### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)
### BUGGY CODE ###

s=[int(0) for i in range(26)]
while True:
    try:
        x=[i for i in input()]
    except EOFError:
        pass
    for i in range(len(x)):
        if 97<=ord(x[i].lower())<=122:
            s[ord(x[i].lower())-97]=s[ord(x[i].lower())-97]+1
for i in range(26):
    print(chr(97+i),":",s[i])

### FIXED CODE ###

s=[int(0) for i in range(26)]
while True:
    try:
        x=input()
        for i in range(len(list(x))):
            if 97<=ord(list(x)[i].lower())<=122:
                s[ord(list(x)[i].lower())-97]=s[ord(list(x)[i].lower())-97]+1
    except EOFError:
        break
for i in range(26):
    print(chr(97+i),":",s[i])
### BUGGY CODE ###

N, M = [int(_) for _ in input().split()]

paths = [[0] * (N + 1) for _ in range(N + 1)]


def has_path(c, t, arrived):
    if c == t: return True
    for i in range(1, N + 1):
        if i in arrived: continue
        if paths[c][i]:
            arrived.append(i)
            if has_path(i, t, arrived):
                return True
            arrived.pop()
    return False


edge = []
for i in range(M):
    a, b = [int(_) for _ in input().split()]
    paths[a][b] = 1
    paths[b][a] = 1
    edge.append((a, b,))

ans = 0
for e in edge:
    paths[e[0]][e[1]] = 0
    paths[e[1]][e[0]] = 0
    if not has_path(e[0], e[1], []):
        ans += 1
    paths[e[0]][e[1]] = 1
    paths[e[1]][e[0]] = 1
print(ans)

### FIXED CODE ###

N, M = [int(_) for _ in input().split()]

paths = [[0] * (N + 1) for _ in range(N + 1)]


def has_path(c, t, arrived):
    if c == t: return True
    for i in range(1, N + 1):
        if i in arrived: continue
        if paths[c][i]:
            arrived.append(i)
            if has_path(i, t, arrived):
                return True
            arrived.pop()
    return False


edge = []
for i in range(M):
    a, b = [int(_) for _ in input().split()]
    paths[a][b] = 1
    paths[b][a] = 1
    edge.append((a, b,))

ans = 0
for e in edge:
    paths[e[0]][e[1]] = 0
    paths[e[1]][e[0]] = 0
    if not has_path(e[0], e[1], []):
        ans += 1
    paths[e[0]][e[1]] = 1
    paths[e[1]][e[0]] = 1
print(ans)
### BUGGY CODE ###

X, K, D = map(int, input().split())
X_a = abs(X)
if X_a - K * D > D:
    print(X_a - K * D)
else:
    while X_a >= D:
        X_a -= D
        K -= 1
    if  K % 2 == 0:
        print(X_a)
    else:
        print(abs(X_a-D))

### FIXED CODE ###

X, K, D = map(int, input().split())
X_a = abs(X)
if X_a - K * D > D:
    print(X_a - K * D)
else:
    K -= X_a // D
    X_a = X_a % D
    while X_a >= D:
        X_a -= D
        K -= 1
    if  K % 2 == 0:
        print(X_a)
    else:
        print(abs(X_a-D))
### BUGGY CODE ###

N, K = map(int, input().split())
S = input()
S += "#"
S_list = []
if S[0] == "0":
    S_list.append(0)

count = 1
before_s = S[0]
for s in S[1:]:
    count += 1
    if before_s != s:
        S_list.append(count-1)
        count = 1
    before_s = s

if S[-2] == "0":
    S_list.append(0)

# print(S_list)

if len(S_list) < 2 * K:
    print(sum(S_list))
else:
    ans = 0
    for i in range(0, len(S_list) - (2 * K), 2):
        left = i
        right = i + 2 * K
        # print(S_list[left:right+1])
        ans = max(ans, sum(S_list[left:right+1]))
    print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
S = input()
S += "#"
S_list = []
if S[0] == "0":
    S_list.append(0)

count = 1
before_s = S[0]
for s in S[1:]:
    count += 1
    if before_s != s:
        S_list.append(count-1)
        count = 1
    before_s = s

if S[-2] == "0":
    S_list.append(0)

# print(S_list)

if len(S_list) < 2 * K:
    print(sum(S_list))
else:
    ans = 0
    ans_list = []
    for i in range(0, len(S_list) - (2 * K), 2):
        left = i
        right = i + 2 * K
        # print(S_list[left:right+1])
        if i == 0:
            ans = sum(S_list[left:right+1])
            ans_list.append(ans)
        else:
            # print(S_list[left-2:left], S_list[right-1:right+1])
            ans = ans - sum(S_list[left-2:left]) + sum(S_list[right-1:right+1])
            ans_list.append(ans)
    print(max(ans_list))
### BUGGY CODE ###

import math
monsterNum, centerDamage, otherDamage = map(int, input().split())
monsterHitpoint = [0] * monsterNum
maxHitpoint = 0

def enough(times):
  result = True
  damageCount = 0
  hitpoint = [monsterHitpoint[i] - otherDamage * times for i in range(monsterNum)]
  for i in range(monsterNum):
    if hitpoint[i] > 0:
      damageCount += math.ceil(hitpoint[i] / (centerDamage - otherDamage))
    if damageCount > times:
      result = False
      break
  return result
  
for i in range(monsterNum):
  monsterHitpoint[i] = int(input())
  if maxHitpoint < monsterHitpoint[i]:
    maxHitpoint = monsterHitpoint[i]
#2分探索
ansFlag = False
subtractionValue = math.ceil(maxHitpoint / otherDamage)
minTimes = subtractionValue
while not ansFlag:
  checkEnough = enough(minTimes)
  subtractionValue = subtractionValue // 2
  if checkEnough and not(enough(minTimes - 1)):
    ansFlag = True
  elif checkEnough:
    minTimes -= subtractionValue
  elif not checkEnough and (enough(minTimes + 1)):
    minTimes += 1
    ansFlag = True
  elif not checkEnough:
    minTimes += subtractionValue + 1
print(minTimes)

### FIXED CODE ###

import math
monsterNum, centerDamage, otherDamage = map(int, input().split())
monsterHitpoint = [0] * monsterNum
maxHitpoint = 0

def enough(times):
  result = True
  damageCount = 0
  hitpoint = [monsterHitpoint[i] - otherDamage * times for i in range(monsterNum)]
  for i in range(monsterNum):
    if hitpoint[i] > 0:
      damageCount += math.ceil(hitpoint[i] / (centerDamage - otherDamage))
    if damageCount > times:
      result = False
      break
  return result
  
for i in range(monsterNum):
  monsterHitpoint[i] = int(input())
  if maxHitpoint < monsterHitpoint[i]:
    maxHitpoint = monsterHitpoint[i]
#2分探索
low, high = 0, math.ceil(maxHitpoint / otherDamage)
while low <= high:
  minTimes = (low + high) // 2
  checkEnough = enough(minTimes)
  if checkEnough and not(enough(minTimes - 1)):
    break
  elif checkEnough:
    high = minTimes - 1
  elif not checkEnough and (enough(minTimes + 1)):
    minTimes += 1
    break
  elif not checkEnough:
    low = minTimes + 1
print(minTimes)
### BUGGY CODE ###

s = input()
l = len(s)
#後ろから見たら一意
i = l-1
try:
    while i>0:
        if s[i]=="r":
            if s[i-5:i+1]=="eraser":
                i-=6
            elif s[i-6:i+1]=="dremer":
                i-=7
        else:
            if s[i-4:i+1]=="erase":
                i-=5
            elif s[i-4:i+1]=="dream":
                i -= 5
    print("YES")
except:
    print("NO")


### FIXED CODE ###

s = input()
l = len(s)
#後ろから見たら一意
"""
tryブロックでsys.exit()を呼ぶと強制終了しない。
"""
import sys
i = l-1
try:
    while i>-1:
        if s[i]=="r":
            if s[i-5:i+1]=="eraser":
                i-=6
            elif s[i-6:i+1]=="dreamer":
                i-=7
            else:
                print("NO")###
                sys.exit()
        else:
            if s[i-4:i+1]=="erase":
                i-=5
            elif s[i-4:i+1]=="dream":
                i -= 5
            else:
                print("NO")###
                sys.exit()
    print("YES")
except:
    pass
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    mi.discard(v)
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=start[0]
ans=[s+1]
nv=s
#print(seen,nv)
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)

print(len(ans))
print(*ans,sep='\n')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  g[u].append(v)
mi=set(range(n))
flg=False
def func(path):
  chk=set(path)
  if len(path)!=2:
    for i,v in enumerate(path):
      nvs=[nv for nv in g[v] if nv in chk]
      if len(nvs)==1:continue
      for nv in nvs:
        if nv==path[(i+1)%len(path)]:continue
        ary=[nv]
        for j,vj in enumerate(path):
          if vj==nv:break
        if i>j:
          ary=path[j:i+1]
        else:
          ary=path[:i+1]+path[j:]
        #print(path,ary,i,j)
        func(ary)
  print(len(path))
  for v in path:
    print(v+1)
  exit()

def dfs(v,seen):
  mi.discard(v)
  for nv in g[v]:
    if seen[nv]!=-1:# 巡回閉路
      seen[nv]=v
      path=[v]
      chk={v}
      while seen[v] not in chk:
        v=seen[v]
        path.append(v)
        chk.add(v)
      path.reverse()
      func(path)
    else:
      seen[nv]=v
      dfs(nv,seen)
      seen[nv]=-1
while mi:
  v=mi.pop()
  seen=[-1]*n
  dfs(v,seen)
print(-1)
exit()
### BUGGY CODE ###

def main():
    def add_divisors(n, d):
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                d[i] += 1
                if i != n // i:
                    d[n // i] += 1
    n = int(input())
    A = list(map(int, input().split()))
    d = {}
    ans = []
    for i in range(1, n + 1):
        d[i] = 0
    for i, a in enumerate(A[::-1]):
        i = n - i
        if d[i] % 2 != a:
            ans.append(str(i))
            add_divisors(i, d)
    print(len(ans))
    print(' '.join(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * n
    ans = []
    for i, a in enumerate(A[::-1]):
        i = n - i
        b = sum(B[i - 1::i])
        if b % 2 != a:
            ans.append(str(i))
            B[i - 1] = 1
    print(len(ans))
    print(' '.join(ans))

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

from collections import deque

h, w = map(int, input().split())
AA = [list(input()) for _ in range(h)]
# AA[h][w]
infi = 10 ** 10
kouho = []
ans = [[infi] * (w) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if AA[i][j] == "#":
            kouho.append((i, j, 0))

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


que = deque(kouho)
while que:
    py, px, d = que.popleft()
    ans[py][px] = d
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if nx < 0 or nx >= w:
            continue
        if ny < 0 or ny >= h:
            continue
        if ans[ny][nx] == infi:
            que.append((ny, nx, d + 1))


cnt = 0
for i in range(h):
    for j in range(w):
        cnt = max(cnt, ans[i][j])

print(cnt)


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
AA = [list(input()) for _ in range(h)]
# AA[h][w]
infi = 10 ** 5
kouho = []
ans = [[infi] * (w) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if AA[i][j] == "#":
            kouho.append((i, j, 0))
            ans[i][j] = 0

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


que = deque(kouho)
while que:
    py, px, d = que.popleft()
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if nx < 0 or nx >= w:
            continue
        if ny < 0 or ny >= h:
            continue
        if ans[ny][nx] == infi:
            ans[ny][nx] = d + 1
            que.append((ny, nx, d + 1))


cnt = 0
for i in range(h):
    for j in range(w):
        cnt = max(cnt, ans[i][j])

print(cnt)
### BUGGY CODE ###


def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]

    N = int(input())
    S = input()

    if S[0]!='B' or S[-1]!='B':
        print(0)
        exit()

    mod = 10**9 + 7
    cnt = 1
    pre = 'B'
    d = 1 #1がleft
    ans = 1

    for i in range(1,N*2):
        if S[i-1]==S[i]:
            if d:
                d = 0
                ans *= cnt%mod
                cnt -= 1
            else:
                d = 1
                cnt += 1
        else:
            if d:
                cnt += 1
            else:
                ans *= cnt%mod
                cnt -= 1

    for i in range(1,N+1):
        ans *= i
        ans %= mod
    if cnt!=0:
        print(0)
        exit()

    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import math
n = int(input())
S = input()
 
RL = [None]*2*n
 
for i in range(2*n):
    if i % 2 == 0:
        if S[i] == 'B':
            RL[i] = 'L'
        else:
            RL[i] = 'R'
 
    else:
        if S[i] == 'B':
            RL[i] = 'R'
        else:
            RL[i] = 'L'
 
if S[0] == 'W' or S[-1] == 'W':
    print(0)
    exit()
 
left = 0
count = 1
mod = 10**9 + 7
 
for check in RL:
    if check == 'L':
        left += 1
    else:
        count = count * left % mod
        left -= 1
 
    if left < 0:
        print(0)
        exit()
 
count = count * math.factorial(n) % mod
 
if left != 0:
    print(0)
else:
    print(count)
### BUGGY CODE ###

import sys
from collections import Counter

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def print_sum(d):
    s = 0
    for k, v in d.items():
        s += k * v
    print(s)


n = I()
al = list(MI())
q = I()

a = Counter(al)

for i in range(q):
    b, c = MI()
    if b in a.keys():
        v = a.pop(b)
        if c in a.keys():
            a[c] += v
        else:
            a[c] = v

    print_sum(a)


### FIXED CODE ###

import sys
from collections import Counter

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n = I()
al = list(MI())
q = I()

a = Counter(al)

s = sum(al)
for _ in range(q):
    b, c = MI()
    if b in a.keys():
        v = a.pop(b)
        if c in a.keys():
            a[c] += v
        else:
            a[c] = v
        s += (c - b) * v
    print(s)
### BUGGY CODE ###

N = int(input())
count = 0

for i in range(357, N+1):

    i_str = str(i)

    if i_str[0] != "3" and i_str[0] != "5" and i_str[0] != "7":
        continue
 
    else:
        thr = i_str.count("3")
        fiv = i_str.count("5")
        sev = i_str.count("7")


        if len(i_str) == thr + fiv + sev:
            if thr > 0:
                if fiv > 0:
                    if sev > 0: 
                        count += 1

print(count)

### FIXED CODE ###

from itertools import product

N = int(input())
num_list = ["3", "5", "7"]
count = 0

for i in range(3, 10):
    for t in (product(num_list, repeat=i)):
        check = t.count("3")*t.count("5")*t.count("7")
        if int("".join(t)) <= N and check:
            count += 1


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

N,K=map(int,input().split())
a=[int(i) for i in input().split()]
mask=0
for k in range(K):
  mask|=1<<k
a.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(N):
  dp[i+1]=(dp[i]|(dp[i]<<a[i]))&mask

def solve(x):
  if len(bin(dp[x]<<a[x]))-2>=K+1:
    return True
  else:
    return False
  
for i in range(-1,N)[::-1]:
  if solve(i):
    break
    
print(N-i-1)

### FIXED CODE ###

from bisect import bisect_left
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()
a=a[:bisect_left(a,K)]
d=[False]*(K)
d[0]=True
curr_max=0
ans=len(a)
for i,a in reversed(list(enumerate(a))):
  if curr_max+a>=K:
    ans=i
  c=curr_max
  for j in range(curr_max+1)[::-1]:
    if j+a<K and d[j]:
      d[j+a]=True
      c=max(c,j+a)
  curr_max=c
print(ans)
### BUGGY CODE ###

n,a,b=map(int,input().split())
mod=10**9+7
def comb(n,k):
    temp=1
    k=min(k,n-k)
    for i in range(k):
        temp*=(n-i)
        temp//=(i+1)

    return temp%mod
#二分累乗法を勉強する
ans=pow(2,n,mod)-1-(comb(n,a)+comb(n,b))
print(ans)

### FIXED CODE ###

n,a,b=map(int,input().split())
mod=10**9+7
def comb(n,k):
    temp=1
    k=min(k,n-k)
    for i in range(1,k+1):
        temp=temp*pow(i,mod-2,mod)
        temp=temp*(n-i+1)%mod

    return temp%mod
#二分累乗法を勉強する
ans=pow(2,n,mod)-1-comb(n,a)-comb(n,b)
print(ans%mod)
### BUGGY CODE ###

import bisect

N = int(input())
Ls = list(map(int, input().split()))
Ls.sort()
# index: 0,...,N-1

ans = 0
for i in range(N-2): # i: 0,...,N-3
    for j in range(i+1, N-1): # j: i+1,...,N-2
        # k: j+1,...,N-1
        rest = Ls[j+1:]
        idx_left  = bisect.bisect_left(rest, Ls[j] - Ls[i] + 1)
        idx_right = bisect.bisect_left(rest, Ls[j] + Ls[i])
        if idx_left < idx_right:
            ans += idx_right - idx_left

print(ans)


### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort() # index: 0,...,N-1

ans = 0
for i in range(N-2): # i: 0,...,N-3
    for j in range(i+1, N-1): # j: i+1,...,N-2
        # k の満たすべき条件:
        # 1. L[k] > L[j] - L[i]
        #     L[k] > L[j] なので自動的に満たす
        # 2. L[k] < L[i] + L[j]
        x = bisect.bisect_left(L, L[i]+L[j])
        # (<L[i]+L[j]), (<L[i]+L[j]), ..., (<L[i]+L[j]) | (L[i]+L[j]<=), (L[i]+L[j]<=), ...
        # | (x) より左側はOK
        # j+1 より右側はOK
        # L[j]<L[i]+L[j] と L[i]+L[j]<=L[x] より L[j]<L[x] つまり j<x
        ans += x - (j + 1)

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

import math
n = int(input())
for i in range(n):
    count = 0
    for x in range(1,int(math.sqrt(n))):
        for y in range(1,int(math.sqrt(n))):
            for z in range(1,int(math.sqrt(n))):
                if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == (i+1):
                    count += 1
    print(count)

### FIXED CODE ###

n = int(input())
ans=[0]*(n+1)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            a = x * x + y * y + z * z + x * y + y * z + z * x
            if n >= a >= 1:
                ans[a] += 1
print(*ans[1:],sep="\n")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans=0
for k in range(2,n):
    for i in range(n-k):
        if a[i]+a[i+k] == k:
            ans+=1
print(ans)

### FIXED CODE ###

import bisect
inf = 10**15
mod = 10**9+7
n = int(input())
a = list(map(int, input().split()))
dicL = [a[i]+i for i in range(n)]
dicR = [i-a[i] for i in range(n)]
dicL.sort()
dicR.sort()
ans = 0
for x in range(n-1):
    indL = bisect.bisect_left(dicL, x)
    indR = bisect.bisect_left(dicR, x)
    countL = 0
    countR = 0
    while indL != n and dicL[indL] == x:
        countL+=1
        indL+=1
    while indR != n and dicR[indR] == x:
        countR+=1
        indR+=1
    ans+=countL*countR
print(ans)
### BUGGY CODE ###

from collections import Counter
s = input()
i = 0
while i < len(s):
    if s[i] == 'd':
        S = s[i:i + 5]
        if i + 6 < len(s):
            if S + s[i + 5] + s[i + 6] == "dreamer":
                i += 7
                if i + 3 < len(s):
                    if s[i:i + 4] == "aser":
                        i += 4
                        continue
                if i + 2 < len(s):
                    if s[i:i + 3] == "ase":
                        i += 3
                        continue
                continue
        if S == "dream":
            i += 5
            continue
        break
    elif s[i] == 'e':
        S = s[i:i + 5]
        if i + 5 < len(s):
            if S + s[i + 5] == "eraser":
                i += 6
                continue
        if S == "erase":
            i += 5
            continue
        break
    if i + 4 >= len(s):
        break
else:
    print("YES")
    exit()
print("NO")

### FIXED CODE ###

from collections import Counter
s = input()
i = 0
while i < len(s):
    if s[i] == 'd':
        S = s[i:i + 5]
        if i + 6 < len(s):
            if S + s[i + 5] + s[i + 6] == "dreamer":
                i += 7
                if i + 3 < len(s):
                    if s[i:i + 4] == "aser":
                        i += 4
                        continue
                if i + 2 < len(s):
                    if s[i:i + 3] == "ase":
                        i += 3
                        continue
                continue
        if S == "dream":
            i += 5
            continue
        break
    elif s[i] == 'e':
        S = s[i:i + 5]
        if i + 5 < len(s):
            if S + s[i + 5] == "eraser":
                i += 6
                continue
        if S == "erase":
            i += 5
            continue
        break
    else:
        break
    if i + 4 >= len(s):
        break
else:
    print("YES")
    exit()
print("NO")