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

import sys, math, collections, heapq, itertools
from bisect import bisect_left
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    Q = int(single_input())
    point = []
    lenq = 0
    constant = 0
    for i in range(Q):
        query = [int(i) for i in line_input()]
        if query[0] == 1:
            constant += query[2]
            point.insert(bisect_left(point, query[1]),query[1])
            lenq += 1
        else:
            j = point[(lenq - 1)//2]
            ans = 0
            for p in point:
                ans += abs(p - j)
            print(j, ans + constant)
    

    return 0
  
if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys, math, collections, heapq, itertools
from bisect import bisect_left
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    Q = int(single_input())
    n, a, b = map(int, line_input())
    left, right = [-a], [a]
    heapq.heapify(left)
    heapq.heapify(right)
    minans =  b
    for i in range(1, Q):
        queri = [int(i) for i in line_input()]
        if queri[0] == 1:
            a, b = queri[1:]
            minans += b
            left_upper = -1 * heapq.heappop(left)
            right_lower = heapq.heappop(right)
            if left_upper <= a <= right_lower:
                heapq.heappush(left, -a)
                heapq.heappush(left, -1 * left_upper)
                heapq.heappush(right, a)
                heapq.heappush(right, right_lower)
            elif a < left_upper:
                minans += left_upper - a
                heapq.heappush(left, -a)
                heapq.heappush(left, -a)
                heapq.heappush(right, left_upper)
                heapq.heappush(right, right_lower)
            else:
                minans += a - right_lower
                heapq.heappush(left, -1 * left_upper)
                heapq.heappush(left, -1 * right_lower)
                heapq.heappush(right, a)
                heapq.heappush(right, a)
        else:
            left_lower = -1 * heapq.heappop(left)
            print(left_lower, minans)
            heapq.heappush(left, -1 * left_lower)
    return 0
  
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

K, S = map(int, input().split())

ans = 0

for i in range(0,K+1):
    for j in range (0,K+1):
        for k in range (0,K+1):
            if (i + j + k) == S:
                ans = ans + 1
                continue
            

print(ans)


### FIXED CODE ###

K, S = map(int, input().split())

ans = 0

for i in range(0,K+1):
    for j in range (0,K+1):
        if (S-K) <= (i + j) <= S:
            ans = ans + 1
            continue
            

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

n=int(input())
a=[0]+list(map(int,input().split()))+[0]
anew=[]
for i in range(n+1):
    anew.append(abs(a[i]-a[i+1]))
for j in range(1,n+1):
    ans=sum(anew)-anew[j-1]-anew[j]+abs(a[j-1]-a[j+1])
    print(ans)

### FIXED CODE ###

n=int(input())
a=[0]+list(map(int,input().split()))+[0]
s=sum(abs(a[i]-a[i+1]) for i in range(len(a)-1))
for i in range(1,n+1):
    print(s-abs(a[i]-a[i+1])-abs(a[i]-a[i-1])+abs(a[i-1]-a[i+1]))
### BUGGY CODE ###

from collections import deque
N = int(input())
E = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
K = 0
E_sorted = sorted(E, key=lambda x:x[0])
ans = {}
V = [deque([i for i in range(1, N)]) for _ in range(N)]
for e in E_sorted:
  a, b = e
  c = 1
  req_K = True
  c = V[a].popleft()
  if c > K:
    K = c
  V[b].remove(c)
  ans[e] = c
print(K)
for e in E:
  print(ans[e])


### FIXED CODE ###

from collections import OrderedDict
N = int(input())
color_parents = [0] * N
tree = [[] for _ in range(N)]
color = OrderedDict()
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  color[(a, b)] = 0
for a in range(N):
  c_p = color_parents[a]
  c = 1
  for b in tree[a]:
    if c == c_p:
      c += 1
    color[(a, b)] = c
    color_parents[b] = c
    c += 1
print(max(color.values()))
for k in color.keys():
  print(color[k])
### BUGGY CODE ###

import itertools
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in itertools.combinations(a,2):
    ans+=(i[0]*i[1])%(10**9+7)
print(ans%(10**9+7))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
k=sum(a)
for i in a:
    k-=i
    ans+=i*k
print(ans%(10**9+7))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
cache = []
for i in range(n-1):
  if s[i] + s[i+1] == 'AC':
    cache.append(i)

for i in range(q):
  l, r = map(int, input().split())
  print(sum(l-1 <= i and i + 1 < r for i in cache))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
li = [0]
for i in range(1, n):
  incr = 1 if s[i-1] + s[i] == 'AC' else 0
  li.append(li[i-1] + incr)

for i in range(q):
  l, r = map(int, input().split())
  print(li[r-1] - li[l-1])
### BUGGY CODE ###

## ABC 072 c
n = int(input())
a = [int(i) for i in input().split()]
a.sort()

ans = 0
cnt = 0
for x in range(a[0]-1, a[-1]+2):
    c = 0
    for i, v in enumerate(a):
        if (abs(x-v) <= 1):
            c += 1
    if (c > cnt):
        ans = x
        cnt = c

print(cnt)


### FIXED CODE ###

## ABC 072 c
from collections import Counter

n = int(input())
a = [int(i) for i in input().split()]
a.sort()

ad = Counter(a)
cnt = 0
for x in range(a[0]-1, a[-1]+2):
    c = ad[x]+ad[x-1]+ad[x+1]
    cnt = max(c,cnt)

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

#-*- coding:utf-8 -*-

n, k, q = map(int, input().split())
a_li = [int(input()) for i in range(q)]

pt_li = []
for i in range(n):
    pt_li.append(k)

for t in range(q):
    for u in range(n):
        pt_li[u] -= 1 
    pt_li[a_li[t]-1] += 1

for v in range(n):
    if pt_li[v] <= -1:
        pt_li[v] = 0

for s in range(n):
     if pt_li[s] == 0:
         print("No")
     else:
         print("Yes")

### FIXED CODE ###

#-*- coding:utf-8 -*-

n, k, q = map(int, input().split())
a_li = [int(input()) for i in range(q)]

b_li = [0]*n

for i in range(q):
    b_li[a_li[i]-1] += 1

for t in range(n):
    pt = k -q + b_li[t]
    if pt > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

def get_longest_count(X, Y):
  m = [[0] * (len(Y) + 1) for i in range(len(X) + 1)]
  for i in range(1, len(X) + 1):
    for j in range(1, len(Y) + 1):
      if X[i - 1] == Y[j - 1]:
        m[i][j] = m[i - 1][j - 1] + 1
      else:
        m[i][j] = max(m[i][j - 1], m[i - 1][j])
  return m[-1][-1]

for i in range(int(input())):
  X = input()
  Y = input()
  print(get_longest_count(X, Y))

### FIXED CODE ###

def get_longest_count(X, Y):
  offsets = [0]
  for y in Y:
    tmp = offsets[:]
    for i, o in enumerate(offsets):
      j = X.find(y, o)
      if j < 0: break
      if i < len(offsets) - 1:
        tmp[i + 1] = min(offsets[i + 1], j + 1)
      else:
        tmp.append(j + 1)
    offsets = tmp
  return len(offsets) - 1

for i in range(int(input())):
  X = input()
  Y = input()
  print(get_longest_count(X, Y))
### BUGGY CODE ###

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

r_idx = set()
g_idx = set()
b_idx = set()

for i, s in enumerate(S):
    if s == "R":
        r_idx.add(i)
    elif s == "G":
        g_idx.add(i)
    elif s == "B":
        b_idx.add(i)

count = 0
if r_idx != set() and g_idx != set() and b_idx != set():
    for r in r_idx:
        for g in g_idx:
            for b in b_idx:
                if abs(g-r) != abs(g-b) and abs(r-b) != abs(g-b) and abs(r-g) != abs(r-b):
                    count += 1
                    
print(count)

### FIXED CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            continue
        k = 2*j - i
        if j < k < n and s[i] != s[k] and s[j] != s[k]:
            cnt += 1
print(s.count('R') * s.count('G') * s.count('B') - cnt)
### BUGGY CODE ###

from collections import deque
s = list(input())
lsts = deque()
kai = 0
cou = 0
for i in range(len(s)):
  s[i] = int(s[i])
s.reverse()
s = deque(s)
cou = 0
le = len(s)
st = 0

for i in s:
  st += i * (10 ** kai)
  amari = st % 2019
  if amari == 0:
    cou += 1
  else:
    lsts.append(amari)  
  kai += 1

while lsts:
  atai = lsts.pop()
  kosu = lsts.count(atai)
  if kosu != 0:
    cou += int(kosu * (kosu+1) / 2)
    for i in range(kosu):
      lsts.remove(atai)

print(cou)

### FIXED CODE ###

from collections import deque
s  = input()[::-1]
lsts = [0] * 2019
kai = 1
cou = 0
st = 0
lsts[0] = 1
for i in s:
  st += int(i) * kai
  st %= 2019
  cou += lsts[st]
  lsts[st] += 1  
  kai = kai * 10 % 2019

print(cou)
### BUGGY CODE ###

x = raw_input()

w,h = [int(i) for i in x.split()]

p = []
for i in range(w):
    p.append(input())

q = []
for i in range(h):
    q.append(input())


cost = 0


iter = w+h


for i in range(iter):

    if(len(p)==0):
        cost += min(q)*(w+1)
        h -= 0
        q.remove(min(q))

    elif(len(q)==0):
        cost += min(p)*(h+1)
        w -= 0
        p.remove(min(p))

    elif(min(p)==min(q) and h>w):
        cost += min(p)*(h+1)
        w -= 1
        p.remove(min(p))

    elif(min(p)<min(q)):
        cost += min(p)*(h+1)
 #       print cost,w,h
        w -= 1
        p.remove(min(p))
    
    else:
        cost += min(q)*(w+1)
  #      print cost,w,h
        h -= 1
        q.remove(min(q))
    

print cost

### FIXED CODE ###

x = raw_input()
w,h = [int(i) for i in x.split()]
p = []
for i in range(w):
    p.append(input())
q = []
for i in range(h):
    q.append(input())
cost = 0
p.sort()
q.sort()
iter = w+h

p_iter = 0
q_iter = 0
for i in range(iter):
    if(w==0):
        cost += q[q_iter]*(w+1)
        h -= 0
        q_iter += 1

    elif(h==0):
        cost += p[p_iter]*(h+1)
        w -= 0
        p_iter += 1

    elif(p[p_iter]==q[q_iter] and h>w):
        cost += p[p_iter]*(h+1)
        w -= 1
        p_iter += 1

    elif(p[p_iter]<q[q_iter]):
        cost += p[p_iter]*(h+1)
        w -= 1
        p_iter += 1
    
    else:
        cost += q[q_iter]*(w+1)
        h -= 1
        q_iter += 1
    
print cost
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(n):
  B.append(A[i])
  B=B[::-1]
print(*B)


### FIXED CODE ###

n=int(input())
A=list(input().split())
print(" ".join(A[::-2]+A[n%2::2]))
### BUGGY CODE ###

N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)

from collections import deque
mindist = N
opt = None
for g,tos in enumerate(es):
    for s in tos:
        q = deque([(s,0)])
        prev = [-1]*N
        while q:
            v,d = q.popleft()
            for to in es[v]:
                if to==g: break
                if prev[to] >= 0: continue
                prev[to] = v
                q.append((to,d+1))
            else:
                continue
            break
        else:
            continue
        if d+1 >= mindist: continue
        mindist = d+1
        opt = [g,v]
        while prev[opt[-1]] >= 0:
            opt.append(prev[opt[-1]])
if opt:
    ans = [o+1 for o in opt]
    print(len(ans))
    print(*ans, sep='\n')
else:
    print(-1)

### FIXED CODE ###

N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)

from collections import deque
tmpdist = N
ans = None
for to in range(N):
    for fr in es[to]:
        dist = [N] * N
        dist[fr] = 0
        prev = [-1] * N
        q = deque([fr])
        while q:
            v = q.popleft()
            if v==to: break
            for w in es[v]:
                if dist[w] < N: continue
                if v==to and w==fr: continue
                dist[w] = dist[v] + 1
                prev[w] = v
                q.append(w)
        else:
            continue
        if dist[to] < tmpdist:
            tmpdist = dist[to]
            ans = set()
            v = to
            while 1:
                ans.add(v+1)
                if prev[v] < 0: break
                v = prev[v]
if ans is None:
    print(-1)
else:
    print(len(ans))
    print(*ans, sep='\n')
### BUGGY CODE ###

import os
import sys
from io import BytesIO, IOBase
from sys import stdin
def input():
    return stdin.readline()

def main():
    N, S = map(int,input().split())
    A = list(map(int,input().split()))
    mod = 998244353
    dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
    dp[0][0]=1
    for i in range(1,N+1) : 
        for j in range(S + 1) : 
            if(j==0):
                dp[i][j]=2**i
            else:
                dp[i][j]+=2*dp[i-1][j]
                dp[i][j]%=mod
                if(j-A[i-1]>=0):
                    dp[i][j]+=dp[i-1][j-A[i-1]]
            dp[i][j]%=mod
    print(dp[N][S]%mod)
    


# fast-io region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input():
    return sys.stdin.readline().rstrip("\r\n")


def write(*args, end="\n"):
    for x in args[:-1]:
        sys.stdout.write(str(x) + " ")
    sys.stdout.write(str(args[-1]))
    sys.stdout.write(end)


def r_array():
    return [int(x) for x in input().split()]


def r_int():
    return int(input())


if __name__ == "__main__":
    main()



### FIXED CODE ###

N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N) : 
    for j in range(S + 1) : 
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod 
        if j + A[i] <= S : 
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= mod
print(dp[N][S])
### BUGGY CODE ###

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

ans = []
for i in range(N-K+1):
  if sum(list(p[i:i+K])) > sum(ans):
    ans = list(p[i:i+K])
    
print((sum(ans)+K)/2)

### FIXED CODE ###

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

rp = sum(list(p[0:K]))
rm = 0
ans = rp
for i in range(N-K):
  rp += p[i+K]
  rm += p[i]
  if rp - rm > ans:
    ans = rp - rm

print((ans+K)/2)
### BUGGY CODE ###

S = str(input())
ans = 0
while S.count('BW') > 0:
  ans += S.count('BW')
  S = S.replace('BW','WB')

print(ans)

### FIXED CODE ###

S = str(input())
ans = 0
B = 1
for i in range(len(S)-1,-1,-1):
  if S[i] == "B":
    ans += len(S[i:-B])
    B += 1

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

a,b = map(int,input().split())
c = a*b
d = 1
ans  = 0
while d%a != 0 or d%b != 0:
    for i in range(2,c+1):
        if b%c != 0:
            b = b*i
        
print(d)

### FIXED CODE ###

a,b = map(int,input().split())
#最大公約数
def gcd(a,b):#a<=b
    while a != 0:
        a,b = b%a,a
    return b
#最小公約数
def lcm(a,b):
    return a*b // gcd(a,b)
print(lcm(a,b))
### BUGGY CODE ###

from sys import stdin

if __name__ == '__main__':
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    P = [int(x) for x in stdin.readline().rstrip().split()]
    E = [((p*(p+1))/2)/p  for p in P]
    maxe = 0
    for i in range(N-K+1):
        val = sum(E[i:i+K])
        if maxe < val:
            maxe = val
    print(maxe)

### FIXED CODE ###

from sys import stdin

if __name__ == '__main__':
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    P = [int(x) for x in stdin.readline().rstrip().split()]
    E = [((p*(p+1))/2)/p  for p in P]
    maxe = sum(E[0:0+K])
    frontval = maxe
    for i in range(1, N-K+1):
        val = frontval - E[i-1] + E[i+K-1]
        frontval = val
        if maxe < val:
            maxe = val
    print(maxe)
### BUGGY CODE ###

from sys import stdin
from itertools import accumulate
n = int(stdin.readline().rstrip())
li = [p for p in range(1,n)]
if n == 1:
    print(0)
else:
    lin = list(accumulate(li))
    print(max(lin))

### FIXED CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
point = n*(n-1)//2
print(point)
### BUGGY CODE ###

#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    S=ST()
    
    can = set([""])
    ans = set()
    for s in S:
        for c in deepcopy(can):
            res = c+s
            if len(res) == 3:
                ans.add(res)
            else:
                can.add(res)
    print(len(ans))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def main():
    N=int(input())
    S=input()[:-1]
    
    can = set([""]) ## 2文字以下で現在構築可能な文字列(最大10+10*10 = 1010)
    ans = set() ## 3文字で現在構築可能な文字列(最大10*10*10 = 1,000)
    for s in S: 
        for c in can.copy(): #途中でcanという集合に追加されるのでcopyする
            res = c+s #2文字以下 + 1文字 で結合する
            if len(res) == 3: #3文字なので暗証番号の候補
                ans.add(res)
            elif len(res) < 3: #2文字以下なのでcanに挿入
                can.add(res)
    print(len(ans))

    """
    copyする回数 = N * len(can) <= 10^3 * N
    for文の走査回数 = N * len(can) <= 10^3 * N
    
    全体で  2 * (10^3 * N)
    N<=3*10^4なので
    2*3* 10^3 * 10^4 = 6 * 10^7 -> 間に合わない？んですか・・・？
    """

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

N,Q = list(map(int,input().split()))
edges = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    edges[a].append(b)
    edges[b].append(a)

add = [0]*(N+1)
for i in range(Q):
    p,x = list(map(int,input().split()))
    add[p] += x

stack = [(1,0)]
ans = [0]*(N+1)
not_checked = [True]*(N+1)
while stack:
    v,cnt = stack.pop()
    ans[v] = cnt+add[v]
    not_checked[v] = False
    for edge in edges[v]:
        if not_checked[edge]:
            stack.append((edge,ans[v]))

for i in range(1,N):
    print(ans[i],end=" ")
print(ans[N])

### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    N,Q = list(map(int,input().split()))
    edges = [[] for i in range(N+1)]
    for i in range(N-1):
        a,b = list(map(int,input().split()))
        edges[a].append(b)
        edges[b].append(a)

    add = [0]*(N+1)
    for i in range(Q):
        p,x = list(map(int,input().split()))
        add[p] += x

    stack = [(1,0)]
    ans = [0]*(N+1)
    not_checked = [True]*(N+1)
    while stack:
        v,cnt = stack.pop()
        ans[v] = cnt+add[v]
        not_checked[v] = False
        for edge in edges[v]:
            if not_checked[edge]:
                stack.append((edge,ans[v]))

    for i in range(1,N):
        print(ans[i],end=" ")
    print(ans[N])

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

N=int(input())
A=list(map(int, input().split()))
aa=0
p,S = 0,0
for i in range(N-1):
    AA = 0
    for j in range(i+1,N):
        AA += A[j]
    aa = A[i]*AA
    S += aa
p = S%1000000007
print(p)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
a,s = 0,0
for i in range(N):
    a += s*A[i]
    s += A[i]
    a %= mod
print(a)
### BUGGY CODE ###

S = input()
Scount = 0
for i in range(len(S)):
    for j in range(1,len(S)):
        if (i+j)<=len(S):
            part_S = S[i:i+j]
            num = int(part_S)
            if num % 3 == 0:
                if num % 673 ==0:
                    Scount += 1
print(Scount)

### FIXED CODE ###

S = input()
from collections import defaultdict
d = defaultdict(int)
before = 0
for i in range(1,len(S)+1):
    now = (int(S[-i])*pow(10,i,2019)+before) % 2019
    d[now] += 1
    before = now
d[0] += 1
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)