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

import math
from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}

    def make(self, x):
        self.p[x] = x

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if x >= y:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            return x


_ncr = {}


def ncr(n, r):
    if n < r:
        return 0
    k = "{}:{}".format(n, r)
    if k not in _ncr:
        _ncr[k] = math.factorial(n) // (math.factorial(n - r) *
                                        math.factorial(r))
    return _ncr[k]


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = ncr(N, 2)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    
    if x != y:
        n = h.get(x, 1) + h.get(y, 1)
        total += ncr(h.get(x, 1), 2) + ncr(h.get(y, 1), 2)
        total -= ncr(n, 2)

        if x in h:
            del h[x]
        if y in h:
            del h[y]
        h[a] = n
    

for v in ans:
    print(v)

### FIXED CODE ###

from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)
### BUGGY CODE ###

input()
l = sorted(map(int, input().split(' ')))

answer = 0
spots = [l.pop()]

while l:
	n = l.pop()
	answer += spots[0]
	spots = spots[1:] + [n] * 2

print(answer)


### FIXED CODE ###

input()
l = sorted(map(int, input().split(' ')))

answer = 0
spots = [l.pop()]
x = len(l)

for i in range(x):
	n = l.pop()
	answer += spots[i]
	spots.append(n)
	spots.append(n)

print(answer)
### BUGGY CODE ###

# B
import sys
N, K = map(int, input().split())
h = list(map(int, input().split()))

cost = [0]*N

cost[0] = 0
for i in range(1,N):
    cost_tmp = [sys.maxsize]*K
    for j in range(0,min(K,i)):
        cost_tmp[j] = abs(h[i - (1+j)] - h[i]) + cost[i - (1+j)]
    cost[i] = min(cost_tmp)

print(cost[-1])

    

### FIXED CODE ###

# B(TLE) 2104ms

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))
cost = np.zeros(N, dtype="int32")

cost[0] = 0
for i in range(1,N):
    start = 0 if i < K else i-K
    cost[i] = np.min(cost[start:i] + np.abs(h[i]-h[start:i]))

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

import numpy as np
N = int(input())
S = list(map(int, input().split()))

mod_count = 0
pre_fugou = 1 ## 前の符号がなんであったか　1ならplus　0ならマイナス

for i in range(N):
    if i==0 and S[i]==0:
        S[i] += 1
        mod_count += 1
        pre_fugou = 1
    elif i==0 and S[i]>0:
        pre_fugou = 1
    elif i==0 and S[i]<0:
        pre_fugou = 0
    else:
        if pre_fugou == 1:
            while True:
                if sum(S[:i+1]) > -1:
                    S[i] -= 1
                    mod_count += 1
                    pre_fugou = 0
                else:
                    pre_fugou = 0
                    break
        elif pre_fugou == 0:
            while True:
                if sum(S[:i+1]) < 1:
                    S[i] += 1
                    mod_count += 1
                    pre_fugou = 1
                else:
                    pre_fugou = 1
                    break
print(mod_count)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
num = float('inf')
for k in [0, 1]:
    s = 0
    tmp = 0
    for i in range(N):
        s += a[i]
        if i % 2 == k:
            if s <= 0:
                tmp += abs(s) + 1
                s = 1
        else:
            if s >= 0:
                tmp += abs(s) + 1
                s = -1
    num = min(tmp, num)

print(num)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = int(input(), 2)
    pc0 = bin(s).count("1")
    ans = []
    for i in range(n):
        k = 1 << (n - 1 - i)
        x = k ^ s
        if x > s:
            pc1 = pc0 + 1
        else:
            pc1 = max(1, pc0 - 1)
        cnt = 0
        while x > 0:
            if cnt == 0:
                pc = pc1
            else:
                pc = bin(x).count("1")
            x %= pc
            cnt += 1
        ans.append(cnt)
    print("\n".join(str(y) for y in ans))
if __name__ == '__main__':
    main()

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
pcx = s.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)
### BUGGY CODE ###

def chmin(a, b):
  if a > b:
    return b
  else:
    return a
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf")]*N
dp[0] = 0
for i in range(N - 1): #ジャンプ地点
	for j in range(1, min(K + 1, N - i)): #ジャンプ距離
		dp[i+j] = chmin(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
	for j in range(1, min(K + 1, N - i)):
		dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])
### BUGGY CODE ###

import sys

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


def root(par, x):
    if par[x] == x:
        return x
    else:
        return root(par, par[x])


def same(par, x, y):
    return root(par, x) == root(par, y)


def unite(rank, par, x, y):
    x = root(par, x)
    y = root(par, y)

    if x == y:
        return

    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def main():
    N, K, L = map(int, readline().split())
    m = map(int, read().split())
    pq = list(zip(m, m))
    pq, rs = pq[:K], pq[K:]

    par = list(range(N))
    rank = [0] * N
    for p, q in pq:
        p -= 1
        q -= 1
        unite(rank, par, p, q)

    par_t = list(range(N))
    rank_t = [0] * N
    for r, s in rs:
        r -= 1
        s -= 1
        unite(rank_t, par_t, r, s)

    cnt = [0] * N
    for i in range(N):
        for j in range(N):
            if same(par, i, j) and same(par_t, i, j):
                cnt[i] += 1

    print(*cnt)


main()


### FIXED CODE ###

from collections import defaultdict
import sys

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


def root(par, x):
    if par[x] == x:
        return x
    else:
        return root(par, par[x])


def unite(rank, par, x, y):
    x = root(par, x)
    y = root(par, y)

    if x == y:
        return

    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def main():
    N, K, L = map(int, readline().split())
    m = map(int, read().split())
    pq = list(zip(m, m))
    pq, rs = pq[:K], pq[K:]

    par = list(range(N))
    rank = [0] * N
    for p, q in pq:
        p -= 1
        q -= 1
        unite(rank, par, p, q)

    par_t = list(range(N))
    rank_t = [0] * N
    for r, s in rs:
        r -= 1
        s -= 1
        unite(rank_t, par_t, r, s)

    pp = [(0, 0)]*N
    dd = defaultdict(list)
    for i in range(N):
        par[i] = root(par, i)
        par_t[i] = root(par_t, i)
        pp[i] = (par[i], par_t[i])
        dd[pp[i]].append(i)

    cnt = [0] * N
    for i in range(N):
        cnt[i] = len(dd[pp[i]])

    print(*cnt)


main()
### BUGGY CODE ###

k=int(input())
from math import gcd
from itertools import product
L=tuple(product([i for i in range(1,k+1)],repeat=3))
s=0
for a,b,c in L:
    a=gcd(a,b)
    s+=gcd(a,c)
print(s)

### FIXED CODE ###

s=0
k=int(input())
from math import gcd
from itertools import product
L=product([i for i in range(1,k+1)],repeat=2)
S=[gcd(a,b) for (a,b) in L]
from collections import Counter
S_counter=Counter(S)
for key,value in S_counter.items():
    for i in range(1,k+1):
        s+=gcd(key,i)*value
print(s)
### BUGGY CODE ###

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted((r, i) for i, (l, r) in enumerate(LR))
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for r, i in W:
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

### FIXED CODE ###

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted(r*U+i for i, (l, r) in enumerate(LR))
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for w in W:
  r, i = divmod(w, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")
### BUGGY CODE ###

N,x= map(int,input().split())
array = list(map(int,input().split()))
result=0
for i in range(0,N-1):
    #i と i+1 が閾値以下じゃなかったら 
    while array[i] + array[i+1] > x:
        if array[i+1]!=0:
            array[i+1]-=1
        else:
            array[i]-=1
        result+=1
print(result)

### FIXED CODE ###

N,x= map(int,input().split())
array = list(map(int,input().split()))
array2=array.copy()
result=0
#TLE pattern
# for i in range(0,N-1):
#     #i と i+1 が閾値以下じゃなかったら 
#     while array[i] + array[i+1] > x:
#         if array[i+1]!=0:
#             array[i+1]-=1
#         else:
#             array[i]-=1
#         result+=1
# print(result)

for i in range(0,N-1):
    if array[i] + array[i+1] > x:
        # if array[i+1] - (array[i] + array[i+1] - x) >= 0:
        #     array[i+1]=array[i+1] - (array[i] + array[i+1] - x)
        if (array[i]+array[i+1])-x <= array[i+1]:
            array[i+1]= array[i+1] - (array[i]+array[i+1]-x)
        else:
            # array[i]=array[i] - (array[i]+array[i+1]) - x - array[i+1]
            array[i]= array[i]-(array[i]-x)
            array[i+1]=0

# print(array2)
# print(array)
print(sum(array2)-sum(array))
### BUGGY CODE ###

# D

S = input()
Q = int(input())

#q = []
#for _ in range(Q):
#  q += [input().split(" ")]

hc = 0

for i in range(Q):
  #qi = q[i]
  qi = input().split(" ")
  if len(qi)==1:
    #S = S[::-1]
    if hc==0:
      hc = 1
    else:
      hc = 0
  else:
    fi = int(qi[1])
    ci = qi[2]
    if hc ==0:
      if fi==1:
        S = ci + S
      else:
        S = S + ci
    else:
      if fi==1:
        S = S + ci
      else:
        S = ci + S

if hc == 1:
  S = S[::-1]
print(S)

### FIXED CODE ###

# D

from collections import deque
S = deque(input())
Q = int(input())

#q = []
#for _ in range(Q):
#  q += [input().split(" ")]

hc = 0

for i in range(Q):
  #qi = q[i]
  qi = input().split(" ")
  if len(qi)==1:
    #S = S[::-1]
    if hc==0:
      hc = 1
    else:
      hc = 0
  else:
    fi = int(qi[1])
    ci = qi[2]
    if hc ==0:
      if fi==1:
        S.appendleft(ci)
      else:
        S.append(ci)
    else:
      if fi==1:
        S.append(ci)
      else:
        S.appendleft(ci)

S = list(S)
if hc == 1:
  S = S[::-1]
print("".join(S))
### BUGGY CODE ###

import bisect
N,M,Q = map(int,input().split())
I = {}
for _ in range(M):
    L,R = map(int,input().split())
    if L not in I:
        I[L] = []
    bisect.insort_right(I[L],R)
for x in I:
  I[x] = sorted(I[x])
A = sorted(list(I.keys()))
for _ in range(Q):
    p,q = map(int,input().split())
    indL = bisect.bisect_left(A,p)
    indR = bisect.bisect_right(A,q)
    cnt = 0
    for i in range(indL,indR):
        a = A[i]
        ind = bisect.bisect_right(I[a],q)
        cnt += ind
    print(cnt)

### FIXED CODE ###

N,M,Q = map(int,input().split())
A = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    L,R = map(int,input().split())
    A[L][R] += 1
B = [[0 for _ in range(N+2)] for _ in range(N+2)]
for i in range(N,0,-1):
    for j in range(1,N+1):
        B[i][j] = A[i][j]+B[i+1][j]+B[i][j-1]-B[i+1][j-1]
for _ in range(Q):
    p,q = map(int,input().split())
    print(B[p][q])
### BUGGY CODE ###

from itertools import product
import math
n = int(input())
scores = []
for a, b, c, in list(product(range(1, n+1), repeat=3)):
    gcd_ab = math.gcd(a, b)
    score = math.gcd(gcd_ab, c)
    scores.append(score)
print(sum(scores))

### FIXED CODE ###

import math
n = int(input())
scores = 0
for a in range(1, n+1):
    for b in range(1, n+1):
        gcd_ab = math.gcd(a, b)
        for c in range(1, n+1):
            score = math.gcd(gcd_ab, c)
            scores += score
print(scores)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def bfs():
    visited[0] = True
    ans[0] = counter[0]
    deq = deque()
    deq.append(0)
    while deq:
        v = deq.popleft()
        for nv in edge[v]:
            if visited[nv] is True:
                continue
            visited[nv] = True
            ans[nv] = ans[v] + counter[nv]
            deq.append(nv)


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {k: 0 for k in range(N)}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

ans = [0 for i in range(N)]
visited = [False for i in range(N)]

bfs()

print(" ".join(list(map(str, ans))))


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def bfs():
    visited[0] = True
    ans[0] = counter[0]
    deq = deque()
    deq.append(0)
    while deq:
        v = deq.popleft()
        for nv in edge[v]:
            if visited[nv] is True:
                continue
            visited[nv] = True
            ans[nv] = ans[v] + counter[nv]
            deq.append(nv)


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {k: 0 for k in range(N)}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

ans = [0 for i in range(N)]
visited = [False for i in range(N)]

bfs()

print(" ".join(list(map(str, ans))))
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))

cnt = 0
p_min = 100000
for i in range(n):
  pi = p[i]
  if i >= 1:
    p_min = min(p[:i])
  if pi <= p_min:
    cnt += 1
print(cnt)


### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))

cnt = 0
p_min = p[0]
for i in range(n):
  pi = p[i]
  if pi <= p_min:
    cnt += 1
    p_min = pi
print(cnt)
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
for i in range(1000):
  t=str(i).zfill(3)
  j=0
  for s_i in s:
    if j<3 and t[j]==s_i:
      j+=1
  if j==3:
    ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(1000):
  t=str(i).zfill(3)
  j=0
  for s_i in s:
    if j<3 and t[j]==s_i:
      j+=1
  if j==3:
    ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())
s = [input() for _ in range(N)]

ss = []
for i in range(N):
    x = list(s[i])
    x.sort()
    y = "".join(x)
    ss.append(y)

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        if ss[i] == ss[j]:
            cnt += 1

print(cnt)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [input() for i in range(N)]
 
ctr = Counter()
ans = 0
for s in S:
    a = ''.join(sorted(list(s)))
    if a in ctr:
        ans += ctr[a]
    ctr[a] += 1
print(ans)
### BUGGY CODE ###

import random, time
start = time.time()
d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]
#貪欲初期解
t = []
memo = [0 for _ in range(26)]
for i in range(d):
    scores = []
    for j in range(26):
        delta_score = 0
        delta_score += s[i][j]
        for k in range(26):
            if j == k:
                continue
            delta_score -= c[k] * (i+1 - memo[k])
        scores.append((delta_score, j))

    scores.sort(key=lambda x: -x[0])
    choice = scores[0][1]
    t.append(choice)
    memo[choice] = i+1

#局所探索
def delta_scoring(t, x, y):
    delta_score = 0
    before_ti, after_ti = 0, d+1
    before_y, after_y = 0, d+1

    for i in range(x):
        if t[i] == t[x]:
            before_ti = i+1
        if t[i] == y:
            before_y = i+1

    for i in range(x+1, d):
        if t[i] == t[x]:
            after_ti = i+1
            break
    for i in range(x+1, d):
        if t[i] == y:
            after_y = i+1
            break

    delta_score -= s[x][t[x]]
    delta_score += s[x][y]
    delta_score -= c[t[x]] * (x + 1 - before_ti) * (after_ti - x - 1)
    delta_score += c[y] * (x + 1 - before_y) * (after_y - x - 1)

    return delta_score

while time.time() - start < 1.9:
    x = random.randint(0, d-1)
    y = random.randint(0, 25)
    if delta_scoring(t, x, y) > 0:
        t[x] = y


for i in range(d):
    print(t[i] + 1)

### FIXED CODE ###

d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]

t = []
memo = [0 for _ in range(26)]
for i in range(d):
    scores = []
    for j in range(26):
        delta_score = 0
        delta_score += s[i][j]
        for k in range(26):
            if j == k:
                continue
            delta_score -= c[k] * (i+1 - memo[k])
        scores.append((delta_score, j))

    scores.sort(key=lambda x: -x[0])
    choice = scores[0][1]
    t.append(choice+1)
    memo[choice] = i+1

print(*t, sep='\n')
### BUGGY CODE ###

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N = int(sys.stdin.readline())

sum = 0

for i in range(N-1):
    sum += (i + 1)

print(sum)

### FIXED CODE ###

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N = int(sys.stdin.readline())

#sum = 0

# for i in range(N-1):
#     sum += (i + 1)

#sum = int((N * (N+1)) / 2 - N)
#sum = (N * (N+1)) / 2 - N

#print(sum)

print((N-1) * N // 2)
### BUGGY CODE ###

island, fune = map(int, input().split(" "))
route = []
for i in range(fune):
    route.append(list(map(int, input().split(" "))))
pos = False
for i in range(fune):
    if route[i][0] == 1:
        for j in range(fune):
            if route[j][1] == island:
                if route[i][1] == route[j][0]:
                    pos = True
                    break
        else:
            continue
        break
print("POSSIBLE") if pos else print("IMPOSSIBLE")

### FIXED CODE ###

island, fune = map(int, input().split(" "))
route = []
for i in range(fune):
    route.append(list(map(int, input().split(" "))))
temp = []
for i in range(fune):
    if route[i][0] == 1:
        temp.append(route[i][1])
for j in range(fune):
    if route[j][1] == island:
        temp.append(route[j][0])


print("POSSIBLE") if len(temp) != len(list(set(temp))) else print("IMPOSSIBLE")
### BUGGY CODE ###

a,b = list(map(int, input().split()))
ans = 0

if 3*a < b:
  print(ans)
elif 3*a == b:
  print(1)
else:
  for i in range(a+1):
    if i > b:
      continue
    elif i == b:
      ans += 1
      continue
    else:
      if i+2*a < b:
        continue
      elif i+2*a == b:
        ans += 1
        continue
      else:
        for j in range(a+1):
          if i+j > b:
            continue
          elif i+j == b:
            ans += 1
            continue
          else:
            if i+j+a < b:
              continue
            elif i+j+a == b:
              ans += 1
              continue
            else:
              for k in range(a+1):
                if i+j+k > b:
                  continue
                elif i+j+k == b:
                  ans += 1
              
  print(ans)

### FIXED CODE ###

k,s = list(map(int, input().split()))
ans = 0
for x in range(k+1):
  mx = min(k, s-x)
  mn = max(0, s-x-k)
  ans += max(0, mx-mn+1)
print(ans)
### BUGGY CODE ###

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

ans = ""
for i in range(1, n+1):
	ans = ans + str(a.index(i)+1) + " "

print(ans.rstrip())


### FIXED CODE ###

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

ans = []
for i in range(1, n+1):
	ans.append("")

for i in range(n):
	tmp = i + 1
	ans[a[i]-1] = str(tmp)
	
print(' '.join(ans))
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1, N):
  ans += i

print(ans)

### FIXED CODE ###

N = int(input())
ans = (N*(N-1))//2
print(ans)