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

def solve(n, h, a):
    size = 1 << ((n + 1) - 1).bit_length()  # 元の配列サイズ以上の最小の二冪 == 最下段
    # 高さに対する美しさの最大値なので、高さ[0,n]の(n+1)要素に対して、segを考える
    seg = [0] * (size * 2 - 1)

    def update(seg, k, x):
        k += size - 1
        seg[k] = x  # 値を更新する
        while k > 0:
            k = (k - 1) // 2  # 親のindex
            seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2])

    def get(seg, a, b, k=0, l=0, r=-1):
        # [a,b)区間の処理結果を返す
        # 注目区間[l,r)
        if r < 0:
            r = size

        if r <= a or b <= l:
            return 0
        # 区間が重ならない

        if a <= l and r <= b:
            return seg[k]
        # 完全被覆

        m = (l + r) // 2
        vl = get(seg, a, b, k * 2 + 1, l, m)
        vr = get(seg, a, b, k * 2 + 2, m, r)
        return max(vl, vr)
        # 部分被覆

    for h_, a_ in zip(h, a):
        update(seg, h_, get(seg, 0, h_) + a_)
        # 1回あたり更新するのは1箇所だから、iを状態にもつ必要はなくて、配列を使い回すことができる
        # 区間maxが高速に計算できればいいから、セグメント木を使えばできる
    return get(seg, 0, n + 1)


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

    n = int(input())
    h = tuple(map(int, input().split()))
    a = tuple(map(int, input().split()))
    print(solve(n, h, a))

# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035


### FIXED CODE ###

class SegmentTree:
    def __init__(self, a: list, e: 'default', f: 'function'):
        n = len(a)
        size = 1 << (n - 1).bit_length()  # 元の配列サイズ以上の最小の二冪 == 最下段
        v = [e] * (size * 2 - 1)
        for i in range(n):
            # size-1個の上段の次、size個目からn個が元の配列の代入位置
            v[size - 1 + i] = a[i]
        for i in range(size - 2, -1, -1):
            v[i] = f(v[i * 2 + 1], v[i * 2 + 2])

        self.n = n  # 元の配列の長さ
        self.size = size  # 元の配列サイズ以上の最小の二冪 == 最下段の要素数
        self.v = v  # Segtreeの配列
        self.e = e  # 初期値
        self.f = f  # 比較関数

    def update(self, k: 'index', x: 'val'):
        k += self.size - 1  # 最下段のindexに変更する
        self.v[k] = x  # 値を更新する
        while k > 0:
            k = (k - 1) // 2  # 親のindex
            self.v[k] = self.f(self.v[k * 2 + 1], self.v[k * 2 + 2])

    def get(self, a, b, k=0, l=0, r=-1):
        # [a,b)区間の処理結果を返す
        # 注目区間[l,r)
        if r < 0:
            r = self.size

        if r <= a or b <= l:
            return self.e
        # 区間が重ならない

        if a <= l and r <= b:
            return self.v[k]
        # 完全被覆

        m = (l + r) // 2
        vl = self.get(a, b, k * 2 + 1, l, m)
        vr = self.get(a, b, k * 2 + 2, m, r)
        return self.f(vl, vr)
        # 部分被覆


def solve(n, h, a):
    seg = SegmentTree([0] * (n + 1), 0, max)
    for i in range(n):
        tmp = seg.get(0, h[i])
        seg.update(h[i], tmp + a[i])
        # 1回あたり更新するのは1箇所だから、iを状態にもつ必要はなくて、配列を使い回すことができる
        # 区間maxが高速に計算できればいいから、セグメント木を使えばできる
    return seg.get(0, n + 1)


if __name__ == '__main__':
    n = int(input())
    h = tuple(map(int, input().split()))
    a = tuple(map(int, input().split()))
    print(solve(n, h, a))

# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035
### BUGGY CODE ###

from heapq import heappush, heappop


def calc(idx, left, right):
    while -left[0] > idx:
        x = -heappop(left)
        heappush(right, x)
    while right[0] < idx:
        x = heappop(right)
        heappush(left, -x)
    ret = 0
    l = -heappop(left)
    r = heappop(right)
    ret += (right[0] - r) * (idx - l) + \
           (l - (-left[0])) * (r - idx)
    heappush(left, -l)
    heappush(right, r)
    heappush(right, idx)
    return ret


def main():
    N = int(input())
    P = list(map(int, input().split()))
    idx = [0] * N
    for i in range(N):
        idx[P[i]-1] = i
    left = [1, 1]
    right = [N, N]
    ans = 0
    for i in range(N)[::-1]:
        x = calc(idx[i], left, right)
        ans += (i+1) * x
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

class BinaryIndexedTree():
    def __init__(self, N):
        self.N = N
        self.arr = [0] * (N+1)

    def query(self, i):
        ret = 0
        i += 1
        while i:
            ret += self.arr[i]
            lsb = i & (-i)
            i -= lsb
        return ret

    def add(self, i, v):
        i += 1
        while i < self.N+1:
            lsb = i & (-i)
            self.arr[i] += v
            i += lsb

    def search(self, x):
        lo = -1
        hi = self.N
        while lo < hi:
            mid = (lo+hi)//2
            if self.query(mid) < x:
                lo = mid + 1
            else:
                hi = mid
        return lo


def main():
    N = int(input())
    P = list(map(int, input().split()))
    idx = [0] * N
    bit = BinaryIndexedTree(N)
    for i in range(N):
        idx[P[i]-1] = i
    ans = 0
    for i in range(N)[::-1]:
        bit.add(idx[i], 1)
        x = bit.query(idx[i])
        l = bit.search(x-1)
        ll = bit.search(x-2)
        r = bit.search(x+1)
        rr = bit.search(x+2)
        tmp = (idx[i]-l) * (rr-r) + (r-idx[i]) * (l-ll)
        ans += (i+1) * tmp
    print(ans)


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

import sys
input = lambda : sys.stdin.readline().rstrip()

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

# N: 処理する区間の長さ

INF = 10**9 + 1

n = q

Len = (n-1).bit_length()
size = 2**Len
tree = [INF]*(2*size)
lazy = [None]*(2*size)

def gindex(l,r):
    L = (l+size)>>1;R=(r+size)>>1
    lc = 0 if l & 1 else (L&-L).bit_length()
    rc = 0 if r & 1 else (R&-R).bit_length()
    for i in range(Len):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1
        
        

def propagates(ids):
    #上から更新
    for i in reversed(ids):
        v = lazy[i]
        if v is None:
            continue
        lazy[2*i]=tree[2*i]=lazy[2*i+1]=tree[2*i+1]=v
        lazy[i]=None

#[l,r)の探索
def update(l,r,x):
    *ids, = gindex(l, r)
    propagates(ids)
    
    L = size+l
    R = size+r
    while L<R:
        if R&1:
            R -= 1
            lazy[R]=tree[R]=x
        if L&1:
            lazy[L]=tree[L]=x
            L+=1
        L>>=1;R>>=1
    #値を更新し終わったら、最小値を下から更新
    for i in ids:
        if 2*i+1<size*2:
            tree[i]=min(tree[i*2],tree[i*2+1])
        
def query(l, r):
    *ids, = gindex(l, r)
    propagates(ids)
    L = size + l
    R = size + r
    s = INF
    while L<R:
        if R&1:
            R-=1
            s = min(s,tree[R])
        if L&1:
            s = min(s,tree[L])
            L+=1
        L>>=1;R>>=1
    return s

import bisect



for x, start, last in stx:
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    update(l, r, x)

for i, j in enumerate(d):
    res = query(i, i + 1)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)
    



### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()

from heapq import heappush, heappop 

running = []
events = []
delete = set()

n, q = map(int, input().split())
for _ in range(n):
    s, t, x = map(int, input().split())
    time = max(s - x, 0)
    if t - x < 0:
        continue
    events.append((s - x, x, 1)) # 追加イベント
    events.append((t - x, x, 0)) # 削除イベント
events.sort()
ans = []
idx = -1
for _ in range(q):
    d = int(input())
    if d >= events[-1][0]:
        print(-1)
        #ans.append(-1)
        continue
    while events[idx + 1][0] <= d:
        idx += 1
        if events[idx][2] == 1:
            heappush(running, events[idx][1])
            delete.discard(events[idx][1])
        else:
            delete.add(events[idx][1])
    flag = 1
    while running:
        x = heappop(running)
        if x not in delete:
            heappush(running, x)
            print(x)
            #ans.append(x)
            flag = 0
            break
    if flag:
        print(-1)
### BUGGY CODE ###

import sys
from collections import deque


def I(): return int(sys.stdin.readline().rstrip())


def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))


def S(): return sys.stdin.readline().rstrip()


def LS(): return list(sys.stdin.readline().rstrip().split())


N = I()
s = []
ans = 0
for i in range(N):
    s.append(''.join(sorted(S())))

for i in range(N-1):
    for q in range(i+1,N):
        if s[i] == s[q]:
            ans += 1

print(ans)


### FIXED CODE ###

import sys
import collections


def I(): return int(sys.stdin.readline().rstrip())


def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))


def S(): return sys.stdin.readline().rstrip()


def LS(): return list(sys.stdin.readline().rstrip().split())


N = I()
s = []
ans = 0
for i in range(N):
    s.append(''.join(sorted(S())))

c = collections.Counter(s)

for i in set(s):
    n = c[i]
    ans += n * (n-1) // 2
print(ans)
### BUGGY CODE ###

def lagrange_interpolation(X, Y, mod):
    # ラグランジュ補間
    # n 個の条件から n-1 次多項式を作る
    n = len(X)
    g = [0]*(n+1)
    g[0] = 1
    for i, x in enumerate(X):
        for j in range(i, -1, -1):
            g[j+1] += g[j] * (-x) % mod
    res = [0]*n
    for x, y in zip(X, Y):
        f = g[:]
        denom = 0
        v = 1
        pow_x = [1]  # x の idx 乗
        for _ in range(n-1):
            v = v * x % mod
            pow_x.append(v)
        pow_x.reverse()  # n-1 乗 ~ 0 乗
        for i, po in enumerate(pow_x):
            f_i = f[i]
            f[i+1] += f_i * x % mod  # f = g / (x - x_i) を組立除法で求める
            denom = (denom + f_i * po)# % mod
        denom_inv = pow(denom, mod-2, mod)
        for i, f_i in enumerate(f[:n]):
            res[i] += (f_i * y * denom_inv)# % mod # 逐次除算したほうが良いかは場合によりそう
    return [v % mod for v in res]

p = int(input())
A = list(map(int, input().split()))
if p==2 and A==[1, 0]:  # AC 回避
    while True:
        print(-1)
ans = lagrange_interpolation(list(range(p)), A, p)
print(" ".join(map(str, ans[::-1])))


### FIXED CODE ###

# AC 回避した https://atcoder.jp/contests/abc137/submissions/6845103 の再提出

def lagrange_interpolation(X, Y, mod):
    # ラグランジュ補間
    # n 個の条件から n-1 次多項式を作る
    n = len(X)
    g = [0]*(n+1)
    g[0] = 1
    for i, x in enumerate(X):
        for j in range(i, -1, -1):
            g[j+1] += g[j] * (-x) % mod
    res = [0]*n
    for x, y in zip(X, Y):
        f = g[:]
        denom = 0
        v = 1
        pow_x = [1]  # x の idx 乗
        for _ in range(n-1):
            v = v * x % mod
            pow_x.append(v)
        pow_x.reverse()  # n-1 乗 ~ 0 乗
        for i, po in enumerate(pow_x):
            f_i = f[i]
            f[i+1] += f_i * x % mod  # f = g / (x - x_i) を組立除法で求める
            denom = (denom + f_i * po)# % mod
        denom_inv = pow(denom, mod-2, mod)
        for i, f_i in enumerate(f[:n]):
            res[i] += (f_i * y * denom_inv)# % mod # 逐次除算したほうが良いかは場合によりそう
    return [v % mod for v in res]

p = int(input())
A = list(map(int, input().split()))
ans = lagrange_interpolation(list(range(p)), A, p)
print(" ".join(map(str, ans[::-1])))
### BUGGY CODE ###

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

for _ in range(M):
    B, C = list(map(int, input().split(' ')))
    A.extend([C]*B)
    
A = sorted(A)
print(sum(A[-N:]))

### FIXED CODE ###

import collections
N, M = list(map(int, input().split(' ')))
A  = list(map(int, input().split(' ')))
dic = dict(collections.Counter(A))
for _ in range(M):
    B, C = list(map(int, input().split(' ')))
    if C in dic.keys():
        dic[C] += B
    else:
        dic[C] = B
l = 0
su = 0
for key in reversed(sorted(dic.keys())):
    l += dic[key]
    if l < N:
        su += key*dic[key]
    else:
        su += key*(dic[key]+(N-l))
        break
print(su)
### BUGGY CODE ###

s=input()
endlist=[]
list=[]
a=len(s)
for i in range(a):
  endlist.append(0)
for j in range(a):
  if s[j]=='R':
    list.append(1)
  else:
    list.append(-1)
b=0
if a%2==0:
  for k in range(a):
    b=k
    for l in range(a):
      b += list[b]
    endlist[b] += 1
else:
  for k in range(a):
    b=k
    for l in range(a-1):
      b += list[b]
    endlist[b] += 1
print(*endlist)

### FIXED CODE ###

S=input()
dp=[0]*len(S)
a=0
for i in range(len(S)):
  if S[i]=='R':
    a+=1
  else:
    dp[i]+=a//2
    dp[i-1]+=a-a//2
    a=0
for i in range(len(S)-1,-1,-1):
  if S[i]=='L':
    a+=1
  else:
    dp[i]+=a//2
    dp[i+1]+=a-a//2
    a=0
print(*dp)
### BUGGY CODE ###

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.append(0)
X.sort()
ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0] * (ma+1) for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  cnt=X[i]
  for j in range(1,N+1):
    for k in range(ma+1):
      if k < cnt:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  if x*A<=ma:
    ans+=dp[N][x][x*A]
print(ans)


### FIXED CODE ###

def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)
### BUGGY CODE ###

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

for _ in range(m):
    b, c = map(int, input().split())
    a += [c]*b

a.sort(reverse=True)

print(sum(a[:n]))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [tuple(map(int, input().split())) for _ in range(m)]
bc.sort(reverse=True, key=lambda x: x[1])

bcs = []
for b, c in bc:
    if len(bcs) > n: break
    bcs.extend([c]*b)

a.extend(bcs)
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = str(input())
l,r = [0]*Q,[0]*Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())
    
count_list = []
for i in range(1,N-1):
    if S[i-1] == "A" and S[i] == "C":
        count_list.append(1)
    else:
        count_list.append(0)
    
for j in range(Q):
    sub_count = count_list[l[j]-1:r[j]-1]
    print(sum(sub_count))
        

a = [1,2,3,4]
b = a[0:2]

### FIXED CODE ###

N,Q = map(int,input().split())
S = str(input())
l,r = [0]*Q,[0]*Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())
    
count_list = []
count = 0
count_list.append(0)
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        count += 1
        count_list.append(count)
    else:
        count_list.append(count)
    
for j in range(Q):
    print(count_list[r[j]-1]-count_list[l[j]-1])
### BUGGY CODE ###

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n,*A = get_all_int()

ans = 1
for a in A:
    ans *= a

print(ans if ans <= 10**18 else -1)


### FIXED CODE ###

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n,*A = get_all_int()

if min(A) == 0:
    print(0)
    exit()

ans = 1
for a in A:
    ans *= a

    if ans > 10**18:
        print(-1)
        exit()

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

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(k+1) for _ in range(n+1)]
mod=10**9+7
#i人目までに0個配る方法は1通り
for i in range(n+1):
  dp[i][0]=1

def main():
  for i in range(1,n+1):
    for j in range(1,k+1):
      tmp=dp[i - 1][j] + dp[i][j - 1]
      if tmp>=mod:
        tmp%=mod
      dp[i][j]=tmp
      if j-a[i-1]-1>=0:
        tmp=dp[i][j]-dp[i-1][j-a[i-1]-1]
        if tmp>=mod:
          tmp%=mod
        dp[i][j]=tmp
    #print(dp)   
  print(dp[n][k]%mod)
main()

### FIXED CODE ###

import sys
from itertools import accumulate

def main():
  input=sys.stdin.readline
  n,k=map(int,input().split())
  A=list(map(int,input().split()))
  mod=10**9+7
  dp=[0]*(k+1)
  dp[0]=1
  for a in A:
    dp=list(accumulate(dp))
    #print("accumulated",dp)
    for j,d in enumerate(dp[:k-a],start=a+1):
      dp[j]-=d
    dp=[dpi%mod for dpi in dp]
    #print(dp)
  print(dp[k])
"""
def main():
  dp=[[0]*(k+1) for _ in range(n+1)]
  mod=1000000007
  #i人目までに0個配る方法は1通り
  #for i in range(n+1):
  #  dp[i][0]=1
  for i in range(0,n+1):
    for j in range(0,k+1):
      if i==0 and j==0:
        dp[i][j]=1
        break
      if j==0:
        dp[i][j]=1
        continue
      tmp=dp[i - 1][j] + dp[i][j - 1]
      if tmp>=mod:
        tmp%=mod
      dp[i][j]=tmp
      if j-a[i-1]-1>=0:
        tmp=dp[i][j]-dp[i-1][j-a[i-1]-1]
        if tmp>=mod:
          tmp%=mod
        dp[i][j]=tmp
    #print(dp)   
  print(dp[n][k])"""
main()
### BUGGY CODE ###

s = input()
x = int(input())
n = len(s)

pos = [[] for __ in range(256)]
for i in range(n):
    pos[ord(s[i])].append(i)

f = {}
for c in range(97, 123):
    for i in pos[c]:
        for j in range(i, n):
            f[s[i:j+1]] = 1
    if len(f) >= x:
        break

def cmp(u, v):
    while len(u) < len(v): u = u + '1'
    while len(u) > len(v): v = v + '1'
    return u > v

p = [u for u in f]
for i in range(len(p)):
    for j in range(i+1, len(p)):
        if cmp(p[i], p[j]):
            p[i], p[j] = p[j], p[i]

print(p[x - 1])

### FIXED CODE ###

s = input()
x = int(input())
n = len(s)

pos = [[] for __ in range(256)]
for i in range(n):
    pos[ord(s[i])].append(i)

f = set()
for c in range(97, 123):
    for i in pos[c]:
        for j in range(x):
            f.add(s[i:i+j+1])
    if len(f) >= x:
        break

p = [u for u in f]
p.sort()
print(p[x - 1])
### BUGGY CODE ###

n=int(input())
paper=[]
for _ in range(n):
    a = int(input())
    if a in paper:
        paper.remove(a)
    else:
        paper.append(a)
print(len(paper))

### FIXED CODE ###

n=int(input())
s=set()
for _ in range(n):
    a = input()
    if a in s:
        s.remove(a)
    else:
        s.add(a)
print(len(s))
### BUGGY CODE ###

import numpy as np
n=int(input())
a=list(np.fromstring(input(),int,sep=' '))
a_=list(set(a))
dic={}
ans=0
for i in a_:
    dic[i]=a.count(i)
for i in dic.values():
    ans+=i*(i-1)//2
    
for i in range(n):
    print(ans-(dic[a[i]]-1))

### FIXED CODE ###

import numpy as np
import collections
n=int(input())
a=list(np.fromstring(input(),int,sep=' '))
dic=collections.Counter(a)
ans=0

for i in dic.values():
    ans+=i*(i-1)//2
    
for i in range(n):
    print(ans-(dic[a[i]]-1))
### BUGGY CODE ###

from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(input())
    A = [int(a) for a in input().split()]

    @lru_cache(None)
    def f(i, j):
        if i < 0 or j < 0:
            return -INF
        if i == 0:
            return -INF
        if j == 0:
            return 0
        if j == 1:
            return max(A[:i])
        return max(A[i - 1] + f(i - 2, j - 1), f(i - 1, j))

    print(f(N, math.floor(N / 2)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(input())
    A = [int(a) for a in input().split()]

    @lru_cache(None)
    def f(i, j):
        if i < 0 or j < 0:
            return -INF
        if i == 0:
            return -INF
        if abs(j - i // 2 - 1) >= 2:
            return -INF
        if j == 0:
            return 0
        if j == 1:
            return max(A[:i])
        return max(A[i - 1] + f(i - 2, j - 1), f(i - 1, j))

    print(f(N, math.floor(N / 2)))


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

s = input()
k = int(input())
l = list(s)
for i in range(len(s)-1):
    for j in range(1, len(s)+1):
        if i < j:
            l.append(s[i:j])
l = list(set(l))
l.sort()
print(l[k-1])

### FIXED CODE ###

s = input()
k = int(input())
lis = list()
for i in range(len(s)):
    for j in range(i+1, i+6):
        if s[i:j] not in lis:
            lis.append(s[i:j])
lis = list(set(lis))
lis.sort()
print(lis[k-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
N, T= map(int, input().split())
t=list(map(int, input().split()))
end_t=T
for j in range (0,N):
  end_t=max(end_t, t[j]+T)
R=[]
for i in range (0,end_t):
  R.append(0)
for s in range (0,end_t):#s秒時点で水で照るかっチェック
  for j in range (0,N):
    if t[j]<=s and s-T< t[j]:
      R[s]=1

count=0
for s in range (0, end_t):
  count+=R[s]
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
N, T= map(int, input().split())
t=list(map(int, input().split()))
count=0
for j in range (0,N-1):
  count+=min(T,t[j+1]-t[j])
print(count+T)
### BUGGY CODE ###

import numpy as np
N=int(input())
A=[int(i) for i in input().split()]
B=np.zeros(N)
for a in range(1,N+1)[::-1]:
    if N % a ==0:
        idx=np.arange(a,N+a,a)-1
    else:
        idx=np.arange(a,N,a)-1
    B[a-1] = (A[a-1] - B[idx].sum()) % 2
B=B 
ans=np.where(B!=0)[0]+1
print(len(ans))
if len(ans)!=0:
    print(*ans)

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
B=[0 for _ in range(N)]
def f(a,N):
    l=[]
    m=2*a
    while m<=N:
        l.append(m)
        m+=a
    return l

for a in range(1,N+1)[::-1]:
    idx=f(a,N)
    b_sum=0
    for i in idx:
        b_sum += B[i-1]
    B[a-1] = (A[a-1] - b_sum) % 2
ans=[i+1 for i in range(N) if B[i] != 0]
print(len(ans))
if len(ans)!=0:
    print(*ans)