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

k = int(input())

if k % 2 == 0 or k % 5 == 0:
    print(-1)
else:
    ans = 1
    num = 7
    while True:
        if int(num) % k == 0:
            print(ans)
            break
        else:
            ans += 1
            num += 7 * pow(10, ans - 1, k)
            num %= k


### FIXED CODE ###

k = int(input())

if k % 2 == 0 or k % 5 == 0:
    print(-1)
else:
    ans = 1
    num = 7 % k
    temp = 7 % k
    while True:
        if num % k == 0:
            print(ans)
            break
        else:
            ans += 1
            temp = temp * 10 % k
            num += temp % k
            num %= k
### BUGGY CODE ###

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

trans=[[] for _ in range(Q)]
for i in range(Q):
    B,C=map(int,input().split())
    trans[i].append(B)
    trans[i].append(C)

S=sum(A)
#まずはじめの合計求める

num=[0]
#これに数の出現回数をプロットする
for i in range(1,10**5+1):
    cnt=A.count(i)
    num.append(cnt)

for i in range(Q):
    B=trans[i][0]
    C=trans[i][1]
    change=num[B]*(C-B)
    num[C]+=num[B]
    num[B]-=num[B]
    S+=change
    print(S)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = []
for i in range(Q):
    BC.append(list(map(int,input().split())))

num = [0]*(10**5+1)

S = []
 
#1 iterlation
S.append(sum(A))
for i in range(N):
    num[A[i]]+=1

    
for j in range(Q):
    if num[BC[j][0]] != 0:
        #Bに当たる交換するものがある時
        B = BC[j][0]
        C = BC[j][1]
        S.append(S[-1] + (C - B)*num[B] )
        #S[-1]で合計の一番最新のもの
        dammy = num[B]
        num[B] = 0
        num[C] += dammy
 
    else:
        B = BC[j][0]
        C = BC[j][1]
        S.append(S[-1])

        
for i in range(1,Q+1):
    print(S[i])
### BUGGY CODE ###

N,M= list(map(int, input().split()))
X= list(map(int, input().split()))
X.sort()
div=[]
if N>=M:
    print("0")
else:
    for i in range(M-1):
        div.append(X[i+1]-X[i])
    for i in range(N-1):
        div.pop(div.index(max(div)))
    print(sum(div))

### FIXED CODE ###

N,M= list(map(int, input().split()))
X= list(map(int, input().split()))
X.sort()
div=[]
if N>=M:
    print("0")
else:
    for i in range(M-1):
        div.append(X[i+1]-X[i])
    div.sort()
    print(sum(div[:M-N]))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
s =0
M = 10**9 +7
for i in range(len(A)-1):
  for  j in A[i+1:]:
    s += A[i]*j % M
print(s%M)

### FIXED CODE ###

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

def bipartite(g):
    s = [(0, 1)]
    c = [0] * n
    while s:
        v, color = s.pop()
        c[v] = color
        for node in g[v]:
            if c[node] == c[v]:
                return False, None
            if c[node] == 0:
                s.append((node, -color))
    return True, c

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
b, colors = bipartite(g)
if b:
    x = colors.count(1)
    print(x * (n - x) - m)
else:
    print(n * (n - 1) // 2 - m)


### FIXED CODE ###

def bipartite(g):
    s = [(0, 1)]
    c = [0] * n
    while s:
        v, color = s.pop()
        c[v] = color
        for node in g[v]:
            if c[node] == c[v]:
                return False, None
            if c[node] == 0:
                s.append((node, -color))
    return True, c

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
b, colors = bipartite(g)
if b:
    x = colors.count(1)
    print(x * (n - x) - m)
else:
    print(n * (n - 1) // 2 - m)
### BUGGY CODE ###

def main():
    import sys,heapq
    from collections import defaultdict
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = defaultdict(int)
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x-0.5,x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if int(p[cnt][0]) == p[cnt][0]:
                used[w] += 1
                heapq.heappush(tank,w)
            else:
                used[w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print(kouho)
                break
            else:
                heapq.heappop(tank)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys,heapq
    from collections import defaultdict
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = defaultdict(int)
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x,-x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if w>=0:
                used[w] += 1
                heapq.heappush(tank,w)
            else:
                used[-w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print(kouho)
                break
            else:
                heapq.heappop(tank)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
area = []
h += 2
w += 2
INF = 1000

for i in range(h):
    if i == 0 or i == h-1:
        array = ['#'] * w
    else:
        array = list(input())
        array.insert(0, '#')
        array.append('#')
    area.append(array)

line = []
for i in range(h):
    for j in range(w):
        if area[i][j] == '#':
            line.append(INF)
        else:
            line.append(1)


def bfs(start):
    unsearched_points = deque()
    searched_points = deque()
    distance_matrix = [INF for _ in range(h*w)]
    unsearched_points.append(start)
    distance_matrix[start] = 0
    while len(unsearched_points) > 0:
        current_point = unsearched_points.popleft()
        searched_points.append(current_point)
        for move in (-1, 1, -w, w):
            if line[current_point+move] == 1 and current_point+move not in searched_points:
                unsearched_points.append(current_point+move)
                distance_matrix[current_point+move] = distance_matrix[current_point] + 1
    l = [x for x in distance_matrix if x < INF]
    return max(l)

max_distance = 0
for i in range(len(line)-w):
    if line[i] == INF:
        continue
    else:
        distance = bfs(i)
        if max_distance < distance:
            max_distance = distance

print(max_distance)



### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())

area = [[] for _ in range(h+2)]

for i in range(h+2):
    if i == 0 or i == h+1:
        area[i] = ['#'] * (w+2)
    else:
        area[i] = list(input())
        area[i].insert(0, '#')
        area[i].append('#')

def bfs(i, j):
    distance_matrix = [[1000 for _ in range(w+2)] for _ in range(h+2)]
    distance_matrix[i][j] = 0
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    d = deque()
    d.append([i, j])
    max_distance = 0
    while len(d) > 0:
        x, y = d.popleft()
        for q, v in move:
            if area[x+q][y+v] =='.' and distance_matrix[x+q][y+v] == 1000:
                d.append([x+q,y+v])
                distance = distance_matrix[x][y] + 1
                distance_matrix[x+q][y+v] = distance
                if distance > max_distance:
                    max_distance = distance
    return max_distance

max_distance = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if area[i][j] == '#':
            continue
        else:
            distance = bfs(i, j)
            if distance > max_distance:
                max_distance = distance


print(max_distance)
### BUGGY CODE ###

from subprocess import*
c=[[0]*50for _ in range(50)]
r=0
for a in[*open(0)][1:]:
  a,b=map(run(('factor',str(round(float(a)*10**9))),stdout=PIPE).stdout.split().count,(b'2',b'5'))
  r+=sum(sum(d[max(0,18-b):])for d in c[max(0,18-a):])
  c[a][b]+=1
print(r)

### FIXED CODE ###

c=[[0]*50for _ in range(50)]
r=0
for a in[*open(0)][1:]:
  a=round(float(a)*10**9)
  x=y=0
  while a%2<1:
    a//=2
    x+=1
  while a%5<1:
    a//=5
    y+=1
  r+=sum(sum(d[max(0,18-y):])for d in c[max(0,18-x):])
  c[x][y]+=1
print(r)
### BUGGY CODE ###

n = int(input())
s = input()
ans = float("inf")
for i in range(len(s)):
  ans = min(ans, s[:i].count('W')+s[i:].count('E'))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = float("inf")
E = s.count('E')
W = 0
for i in s:
  if i == 'E':
    E -= 1
    ans = min(ans, E+W)
  else:
    W += 1
    ans = min(ans, E+W-1)
print(ans)
### BUGGY CODE ###

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

cnt = 0
X = []

for k in a:
    X.append(k+1)
    X.append(k)
    X.append(k-1)

for i in X:
    tmplist = []
    for j in a:
        tmplist.append(i-j)
        if cnt < tmplist.count(1) + tmplist.count(0) + tmplist.count(-1):
            cnt = tmplist.count(1) + tmplist.count(0) + tmplist.count(-1)

print(cnt)

### FIXED CODE ###

# 辞書を用意して最大値を取得する

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

cnt = {}

for i in a:
    for j in [-1,0,1]:
        cnt.setdefault(i+j, 0)
        cnt[i+j] += 1

print(max(cnt.values()))
### BUGGY CODE ###

N=int(input())
A=[]
b=0

for i in range(0,N):
    S=input()
    if not S in A:
        b+=1
        A.append(S)
print(b)

### FIXED CODE ###

from collections import Counter
N=int(input())
b=0
S=[]

for i in range(0,N):
    S.append(input())
b=Counter(S)
print(len(b))
### BUGGY CODE ###

import sys

s = input()[::-1]
v = 0
mods = [ 0 for i in range(2019) ]
mods[0] = 1
d = 1

for c in s:
    v += int(c) * d
    #print(v)
    v %= 2019
    d *= 10
    #d %= 2019
    mods[v] += 1

ans = 0
for n in mods:
    ans += (n * (n - 1)) // 2

print(ans)

### FIXED CODE ###

s = input()[::-1] # 右からn桁の数についてループを回していきたいので、文字列を反転させる

sum_of_digits = 0 # 余りの値
cnts = [0] * 2019 # 余りの値ごとに余りが同じ値の数を格納する変数。2019で割る場合、余りは0~2018までの2019通りあるので、リストの長さは2019
cnts[0] = 1 # ※1
d = 1 # sum_of_digitsの計算に使う10の累乗値

# まず余りの値ごとに余りが同じ値の数を数える
for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019 # ※2
    cnts[sum_of_digits] += 1

# 次に余りの値ごとにその組み合わせを計算し、足し合わせる
ans = 0
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

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

import sys,itertools
for s in sys.stdin:
  a=map(int,s.split(" "))
  w=a[0]
  n=len(a)-1
  A=itertools.permutations(a[1:],n)
  s0=1e9
  for e in A:
    s=e[0]+e[-1]
    for i in range(n-1): s+=2*(e[i]*e[i+1])**.5
    if s<s0: s0=s
    if s0<=w: break
  print ["OK","NA"][s0>w]

### FIXED CODE ###

import sys
for s in sys.stdin:
  a=map(int,s.split(" "))
  w=a[0]
  a=sorted(a[1:])
  A=[]
  while a:
    A+=[a.pop(0)]
    if a==[]: break
    A=[a.pop()]+A
    if a==[]: break
    A+=[a.pop()]
    if a==[]: break
    A=[a.pop(0)]+A
  a=A[0]+A[-1]
  for i in range(len(A)-1): a+=2*(A[i]*A[i+1])**.5
  print ["OK","NA"][a>w]
### BUGGY CODE ###

N = int(input())
S = input()
l = []
for i in range(N):  # iはリーダーのインデックス番号
    counter = 0     # counterは向きを変える人数
    for j in range(i):
        if S[j] == "W":
            counter += 1
    for j in range(i+1,N):
        if S[j] == "E":
            counter += 1
    l.append(counter)
print(min(l))

### FIXED CODE ###

# 累積和の手法をとる
# 簡単にいうと要素が ある区間の和 であるようなリストを先に作成しておき
# 必要な時に取り出すという手法である
# 同じ計算過程を何回も繰り返す（上の解法）ことなく結果がでる
N = int(input())
S = input()
w = [0 for _ in range(N)]       # Wを向いている人の番号に１、逆の方角の人に０を割り当てる
sw = [0 for _ in range(N+1)]    # リストwの累積和のリスト、つまり sw[i] は 0~i-1 でWを向いている人の累積和
e = [0 for _ in range(N)]       # Eを向いている人の番号に１、逆の方角の人に０を割り当てる
se = [0 for _ in range(N+1)]    # リストeの累積和のリスト
l = []

for i in range(N):
    if S[i] == "W":
        w[i] = 1
    else:
        e[i] = 1

# 累積和を格納したリストを求める
for i in range(N):
    sw[i+1] = sw[i] + w[i]
    se[i+1] = se[i] + e[i]

# 本計算
for i in range(N):      # i 番目がリーダーだとする
    counter = sw[i] + (se[N] - se[i+1])
    l.append(counter)

print(min(l))
### BUGGY CODE ###

n = int(raw_input())

dict = []
for i in range(n):
    command, word = raw_input().split()
    if command == 'insert':
        dict.append(word)
    else:
        try:
            dict.index(word)
            print 'yes'
        except:
            print 'no'
            pass
        

### FIXED CODE ###

n = int(raw_input())

def makeHash(letter):
    if letter == 'A':
        return 1
    elif letter == 'C':
        return 2
    elif letter == 'G':
        return 3
    elif letter == 'T':
        return 4
    return 0

dict = {}
for i in range(n):
    command, word = raw_input().split()
    key = 0
    if command == 'insert':
         dict[word] = 1
    elif command == 'find':
        if word in dict: 
            print 'yes'
        else:
            print 'no'
### BUGGY CODE ###

N,M = map(int, input().split())
A = [int(a) for a in input().split()]
L = [[int(x) for x in input().split()] for _ in range(M)]

import heapq
from operator import itemgetter
L.sort(key=itemgetter(1))

h = []
for i in range(N):
    heapq.heappush(h, A[i])
    

for i in range(M):
    Bi = L[i][0]
    Ci = L[i][1]
    h_min = h[0]
    while Bi > 0 and Ci > h_min:
        heapq.heappop(h)
        heapq.heappush(h, Ci)
        Bi -= 1
        h_min = h[0]
        
print(sum(h))

### FIXED CODE ###

N,M = map(int, input().split())
A = [int(a) for a in input().split()]
L = [[int(x) for x in input().split()] for _ in range(M)]

import heapq
from operator import itemgetter
L.sort(reverse=True, key=itemgetter(1))

h = []
for i in range(N):
    heapq.heappush(h, A[i])
    

for i in range(M):
    Bi = L[i][0]
    Ci = L[i][1]
    h_min = h[0]
    while Bi > 0 and Ci > h_min:
        temp = heapq.heappop(h)
        heapq.heappush(h, Ci)
        Bi -= 1
        h_min = h[0]
        
print(sum(h))
### BUGGY CODE ###

def main():
    N, W = list(map(int, input().split()))
    DP = [[0 for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        w, v = list(map(int, input().split()))
        for sum_w in range(W+1):
            if sum_w - w >= 0:
               DP[i+1][sum_w] = max(DP[i][sum_w],DP[i][sum_w-w]+v)
            DP[i+1][sum_w] = max(DP[i+1][sum_w],DP[i][sum_w])
    print(max(DP[-1]))

if __name__ == "__main__":
    main()
    pass

### FIXED CODE ###

def main():
    N, W = list(map(int, input().split()))
    DP = [[0 for i in range(W+1)] for j in range(N+1)]
    for i in range(N):
        w, v = list(map(int, input().split()))
        for sum_w in range(W+1):
            if sum_w - w >= 0:
               DP[i+1][sum_w] = max(DP[i][sum_w],DP[i][sum_w-w]+v)
            DP[i+1][sum_w] = max(DP[i+1][sum_w],DP[i][sum_w])
    print(max(DP[-1]))

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

#!/usr/bin/env python3
# %%
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import itertools
from math import acos, cos, sin

# %%
N, K = map(int, readline().split())
m = map(int, read().split())
XYC = zip(m, m, m)
X, Y, C = zip(*XYC)
X = [complex(x, y) for x, y in zip(X, Y)]


# %%
def cross_pts(x1, r1, x2, r2):
    D = abs(x1 - x2)
    if r1 + r2 <= D:
        return
    if abs(r1 - r2) >= D:
        return
    theta = acos((r1 * r1 + D * D - r2 * r2) / (2 * r1 * D))
    z = complex(cos(theta), sin(theta)) * r1 / D
    yield x1 + (x2 - x1) * z
    yield x1 + (x2 - x1) * z.conjugate()


# %%
def test(cost):
    R = [cost / c for c in C]

    def gen_y():
        for i in range(N):
            yield X[i].imag - R[i]
            yield X[i].imag + R[i]
        for i, j in itertools.combinations(range(N), 2):
            for x in cross_pts(X[i], R[i], X[j], R[j]):
                yield x.imag
    Y = sorted(gen_y())
    for y1, y2 in zip(Y, Y[1:]):
        y = (y1 + y2) / 2
        event = []
        for i in range(N):
            if R[i] < abs(X[i].imag - y):
                continue
            dx = (R[i] ** 2 - (X[i].imag - y) ** 2) ** .5
            event.append((X[i].real - dx, 1))
            event.append((X[i].real + dx, -1))
        event.sort()
        n = 0
        best_n = 0
        for _, dn in event:
            n += dn
            if n > best_n:
                best_n = n
        if best_n >= K:
            return True
    return False


# %%
left = 0
right = 150000
for _ in range(50):
    x = (left + right) / 2
    if test(x):
        right = x
    else:
        left = x
print(right)


### FIXED CODE ###

import sys
from cmath import rect
import numpy as np
import numba
from numba import njit
i8 = numba.int64

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

eps = 1e-9

@njit((numba.complex128, numba.float64) * 2, cache=True)
def cross_circles(c1, r1, c2, r2):
    d = abs(c1 - c2)
    if d <= abs(r1 - r2) or r1 + r2 <= d:
        return None
    cos_theta = (r1 * r1 + d * d - r2 * r2) / (2 * r1 * d)
    theta = np.arccos(cos_theta)
    z1 = (c2 - c1) * rect(r1 / d, theta)
    z2 = (c2 - c1) * rect(r1 / d, -theta)
    return (c1 + z1, c1 + z2)

@njit
def test(Z, C, t):
    R = t / C
    cand = list(Z)
    for j in range(len(Z)):
        for i in range(j):
            points = cross_circles(Z[i], R[i], Z[j], R[j])
            if points is not None:
                for p in points:
                    cand.append(p)
    cand = np.array(cand)
    cnt = np.zeros(len(cand), np.int64)
    for i in range(len(Z)):
        cnt += np.abs(cand - Z[i]) <= R[i] + eps
    return np.any(cnt >= K)

N, K = map(int, readline().split())
nums = np.array(read().split(), np.float64)

Z = nums[::3] + 1j * nums[1::3]
C = nums[2::3]

l = 0
r = 10**9
for _ in range(100):
    m = (l + r) / 2
    if test(Z, C, m):
        r = m
    else:
        l = m

print(r)
### BUGGY CODE ###

s = input()
n = len(s)
dp = [[0] * 13 for _ in range(n)]
mod = 10**9 + 7

if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

for i in range(1,n):
    if s[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i][(j * 10 + k) % 13] += dp[i-1][j]
    else:
        k = int(s[i])
        for j in range(13):
            dp[i][(j * 10 + k) % 13] += dp[i-1][j]
    for j in range(13):
        dp[i][j] %= mod

print(dp[n-1][5]%mod)


### FIXED CODE ###

s = input()
n = len(s)
dp = [[0] * 13 for _ in range(n)]
mod = 10**9 + 7

if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

for i in range(1,n):
    if s[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i][(j * 10 + k) % 13] += dp[i-1][j]
    else:
        k = int(s[i])
        for j in range(13):
            dp[i][(j * 10 + k) % 13] += dp[i-1][j]
    for j in range(13):
        dp[i][j] %= mod

print(dp[n-1][5]%mod)
### BUGGY CODE ###

def find():
    h,w,m=map(int,input().split())
    idx=[]

    for i in range(m):
      var=list(map(int,input().split()))
      idx.append(var)


    r={}
    c={}
    maze=[[0 for j in range(w)]for i in range(h)]

    for i in idx:
      maze[i[0]-1][i[1]-1]=1
      r.setdefault(i[0]-1,0)
      r[i[0]-1]+=1
      c.setdefault(i[1]-1,0)
      c[i[1]-1]+=1

    ans=0
    maxval=0



    row=[]
    col=[]
    maxr=max(r.values())
    maxc=max(c.values())
    for i in range(h):
      r.setdefault(i,0)
      if r[i]==maxr:
        row.append(i)
      

    for j in range(w):
      c.setdefault(j,0)
      if c[j]==maxc:
        col.append(j)
    
    for i in row:
      for j in col:
        if(maze[i][j]==0):
          return maxc+maxr
         
        
    return maxc+maxr-1
 
print(find())

### FIXED CODE ###

def find():
    h,w,m=map(int,input().split())
    idx=[]


    for i in range(m):
      var=list(map(int,input().split()))
      idx.append(var)


    r={}
    c={}
    #maze=[[0 for j in range(w)]for i in range(h)]
    mz={}

    for i in idx:
      mz.setdefault((i[0]-1,i[1]-1),0)
      mz[(i[0]-1,i[1]-1)]=1
      #maze[i[0]-1][i[1]-1]=1
      r.setdefault(i[0]-1,0)
      r[i[0]-1]+=1
      c.setdefault(i[1]-1,0)
      c[i[1]-1]+=1

    ans=0
    maxval=0



    row=[]
    col=[]
    maxr=max(r.values())
    maxc=max(c.values())
    for i in range(h):
      r.setdefault(i,0)
      if r[i]==maxr:
        row.append(i)
      

    for j in range(w):
      c.setdefault(j,0)
      if c[j]==maxc:
        col.append(j)
    
    for i in row:
      for j in col:
        mz.setdefault((i,j),0)
        if(mz[(i,j)]==0):
          return maxc+maxr
         
    return maxc+maxr-1
 
print(find())
### BUGGY CODE ###

n = int(input())
print(sum(i for i in range(1, n)))


### FIXED CODE ###

n = int(input())
print(n*(n-1) // 2)
### BUGGY CODE ###


from functools import reduce

def gcd(a,b):
  x = max([a,b])
  y = min([a,b])
  while y:
    x, y = y, x % y
  return x

def gcd_list(nums):
  return reduce(gcd, nums)

n = int(input())

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


ans = 0
for i in range(n):
      tmp_list = a[:i] + (a[i+1:])
      #print(tmp_list)
      tmp = gcd_list(tmp_list)
      if ans < tmp:
            ans = tmp

print(ans)


### FIXED CODE ###

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


def gcd(a,b):
  x = max([a,b])
  y = min([a,b])
  while y:
    x, y = y, x % y
  return x

L = [0]
R = [0]

for i in range(N):
    L.append(gcd(L[-1], A[i]))
    
for i in reversed(range(N)):
    R.append(gcd(R[-1], A[i]))

R = list(reversed(R))


ans = 1
for i in range(N-1):
    ans = max(ans, gcd(L[i], R[i+1]))

ans = max(ans, R[1])
ans = max(ans, L[-2])

print(ans)
#print(R)
#print(L)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
l=[0]*q
for i in range(q):
    b,c=map(int,input().split())
    l[i]=(b,c)
book={}
for i in a:
    if i in book:
        book[i]+=1
    else:
        book[i]=1

for i in range(q):
    ans=0
    if l[i][0] in book:
        if l[i][1] in book:
            book[l[i][1]]+=book[l[i][0]]
            book.pop(l[i][0])
        else:
            book[l[i][1]]=book[l[i][0]]
            book.pop(l[i][0])
    for j in book:
        ans+=book[j]*j
    print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
l=[0]*q
ans=sum(a)
for i in range(q):
    b,c=map(int,input().split())
    l[i]=(b,c)
book={}
for i in a:
    if i in book:
        book[i]+=1
    else:
        book[i]=1

for i in range(q):
    if l[i][0] in book:
        if l[i][1] in book:
            ans+=(l[i][1]-l[i][0])*book[l[i][0]]
            book[l[i][1]]+=book[l[i][0]]
            book[l[i][0]]=0
        else:
            ans+=(l[i][1]-l[i][0])*book[l[i][0]]
            book[l[i][1]]=book[l[i][0]]
            book[l[i][0]]=0
    print(ans)