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

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

A_dash = []
for i, A_i in enumerate(A):
    A_dash.append(A_i - (i))
A_dash.sort()

tmp_ans = sum(A_dash)
ans = 0
left, right = min(A_dash), max(A_dash)
mid = (left+right)//2
ans_left, ans_mid, ans_right = 0, 0, 0
for A_dash_i in A_dash:
    ans_left += abs(A_dash_i - (mid-1))
    ans_mid += abs(A_dash_i - (mid))
    ans_right += abs(A_dash_i - (mid+1))

while not (ans_left >= ans_mid and ans_mid <= ans_right):
    mid = (left+right)//2
    ans_left, ans_mid, ans_right = 0, 0, 0
    for A_dash_i in A_dash:
        ans_left += abs(A_dash_i - (mid-1))
        ans_mid += abs(A_dash_i - (mid))
        ans_right += abs(A_dash_i - (mid+1))
    if ans_left < ans_mid:
        right = (left+right)//2
    else:
        left = (left+right)//2

print(ans_mid)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A_dash = []
for i, A_i in enumerate(A):
    A_dash.append(A_i-(i+1))
A_dash.sort()

med = A_dash[N//2]

ans = 0
for i, A_i in enumerate(A_dash):
    ans += abs(A_i - (med))

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

n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

dp=[[0 for i in range(k+1)] for j in range(n+1)]

for i in range(n-1,-1,-1):
  for j in range(k+1):
    if j < e[i][0]:
      dp[i][j]=0
    else:
      dp[i][j]=max(dp[i+1][j],dp[i+1][j-e[i][0]]+e[i][1])

print(dp[0][-1])

### FIXED CODE ###

n,k=(int(i) for i in input().split())

e = [[int(i) for i in input().split()] for j in range(n)]
#print(e)

dp=[[0 for i in range(k+1)] for j in range(n+1)]

for i in range(n-1,-1,-1):
  for j in range(k+1):
    if j < e[i][0]:
      dp[i][j]=dp[i+1][j]
    else:
      dp[i][j]=max(dp[i+1][j],dp[i+1][j-e[i][0]]+e[i][1])

print(max(dp[0]))
### BUGGY CODE ###


import sys
input=sys.stdin.readline
h,w,k=map(int,input().split())
sx,sy,tx,ty=map(int,input().split())
b=[[-1]*(w+2)]
for i in range(h):
  s=input()
  bb=[-1]
  for j in s:
    if j==".":bb.append(0)
    else:bb.append(-1)
  bb.append(-1)
  b.append(bb)
b.append([-1]*(w+2))
from collections import deque
d=deque()
d.append((sx,sy))
s=set()
while d:
  x,y=d.popleft()
  if (x,y) in s:
    s.discard((x,y))
    continue
  if x==tx and y==ty:
    exit(print(b[x][y]))
  for i in range(1,k+1):
    if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
    d.append((x-i,y))
    if b[x-i][y]!=0:
      s.add((x-i,y))
    b[x-i][y]=b[x][y]+1
  for i in range(1,k+1):
    if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
    d.append((x+i,y))
    if b[x+i][y]!=0:
      s.add((x+i,y))
    b[x+i][y]=b[x][y]+1
  for j in range(1,k+1):
    if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
    d.append((x,y-j))
    if b[x][y-j]!=0:
      s.add((x,y-j))
    b[x][y-j]=b[x][y]+1
  for j in range(1,k+1):
    if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
    d.append((x,y+j))
    if b[x][y+j]!=0:
      s.add((x,y+j))
    b[x][y+j]=b[x][y]+1
print(-1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,k=map(int,input().split())
si,sj,ti,tj=map(int,input().split())
si-=1
sj-=1
ti-=1
tj-=1
b=[input()for _ in range(h)]
ans=[[-1]*w for _ in range(h)]
ans[si][sj]=0
from collections import deque
d=deque()
d.append((si,sj))
while d:
  x,y=d.popleft()
  if x==ti and y==tj:
    exit(print(ans[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or b[xx][yy]=="@":break
      if 0<=ans[xx][yy]<=ans[x][y]:break
      if ans[xx][yy]==-1:d.append((xx,yy))
      ans[xx][yy]=ans[x][y]+1
print(-1)
### BUGGY CODE ###

import numpy
from bisect import bisect_left, bisect_right

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

ans=A_sum[N-1]
for m in range(2,N-1):
  sum_left=A_sum[m-1]
  i=bisect_left(A_sum,sum_left/2)
  sum1=A_sum[i]
  if i!=0:
    if A_sum[i]+A_sum[i-1]>sum_left:
      sum1=A_sum[i-1]
  sum2=sum_left-sum1

  sum_right=A_sum[N-1]-sum_left
  i=bisect_left(A_sum,sum_left+sum_right/2)
  sum3=A_sum[i]-sum_left
  if i!=m:
    if A_sum[i]+A_sum[i-1]-2*sum_left>sum_right:
      sum3=A_sum[i-1]-sum_left
  sum4=sum_right-sum3
  max_sum=max(sum1,sum2,sum3,sum4)
  min_sum=min(sum1,sum2,sum3,sum4)
  dif=max_sum-min_sum
  if dif<ans:
    ans=dif

print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
from itertools import accumulate

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

ans=A_sum[N-1]
for m in range(2,N-1):
  sum_left=A_sum[m-1]
  i=bisect_left(A_sum,sum_left/2)
  sum1=A_sum[i]
  if i!=0:
    if A_sum[i]+A_sum[i-1]>sum_left:
      sum1=A_sum[i-1]
  sum2=sum_left-sum1

  sum_right=A_sum[N-1]-sum_left
  i=bisect_left(A_sum,sum_left+sum_right/2)
  sum3=A_sum[i]-sum_left
  if i!=m:
    if A_sum[i]+A_sum[i-1]-2*sum_left>sum_right:
      sum3=A_sum[i-1]-sum_left
  sum4=sum_right-sum3
  max_sum=max(sum1,sum2,sum3,sum4)
  min_sum=min(sum1,sum2,sum3,sum4)
  dif=max_sum-min_sum
  if dif<ans:
    ans=dif

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

# -*- coding: utf-8 -*-
#https://atcoder.jp/contests/abc141/tasks/abc147_d
import sys
#import collections

n= int(input())

tmp = input().split()
s = list(map(lambda a: int(a), tmp))

total=0
a=[]
b=[]
c=[]
for i in range(0,60):
	a.append(0)
	b.append(0)
	c.append(0)

tmp = s[0]
for j in range(0,60):
	if(tmp==0):
		break
	if(tmp%2==1):
		a[j]+=1
	tmp=tmp//2

tmp = s[n-1]
for j in range(0,60):
	if(tmp==0):
		break
	if(tmp%2==1):
		c[j]+=1
	tmp=tmp//2

for i in range(1,n-1):
	tmp = s[i]
	for j in range(0,60):
		if(tmp==0):
			break
		if(tmp%2==1):
			b[j]+=1
		tmp=tmp//2

#print(s)
#print(a)
#print(b)
#print(c)

total=0
for j in range(60,0,-1):
	total*=2
	total=total+(a[j-1]+b[j-1]+c[j-1])*(n-a[j-1]-b[j-1]-c[j-1])
#	print(total)

total=total%1000000007

print(total)





### FIXED CODE ###

# -*- coding: utf-8 -*-
#https://atcoder.jp/contests/abc141/tasks/abc147_d
import sys
#import collections

n= int(input())

tmp = input().split()
s = list(map(lambda a: int(a), tmp))

total=0
a=[]
for i in range(0,60):
	a.append(0)

for i in range(0,n):
	tmp = s[i]
	for j in range(0,60):
		if(tmp==0):
			break
		if(tmp%2==1):
			a[j]+=1
		tmp=tmp//2

total=0
for j in range(60,0,-1):
	total*=2
	if(a[j-1]>0):
		total=total+(a[j-1])*(n-a[j-1])
	if(total>1000000007):
		total=total%1000000007
total=total%1000000007

print(total)
### BUGGY CODE ###

s=input()
q=int(input())
for _ in range(q):
    a=[x for x in input().split()]
    if len(a)==1:
        s=s[::-1]
    else:
        if a[1]=='1':
            s=a[2]+s
        else:
            s+=a[2]

print(s)


### FIXED CODE ###

from collections import deque
que=deque(input())
rev=False
for _ in range(int(input())):
    t=input()
    if t=='1':
        rev=not rev
    else:
        tt,f,c=t.split()
        if (f=='1' and rev==False)  or (f=='2' and rev):
            que.appendleft(c)
        else:
            que.append(c)
if rev:
    que.reverse()

print(''.join(que))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# 入力
N, K = map(int, input().split())
H = [int(i) for i in input().split()]

# DPテーブルを用意
dp = [float("inf")] * N
# 初期値をセット
dp[0] = 0

# 足場0から順次最小コストを決定する
for i in range(1, N):
    # for j in range(1, K+1):
        # if i + j < N:
            # dp[i+j] = min(dp[i+j], (dp[i] + abs(H[i] - H[i+j])))
    dp[i] = min([dp[i-j] + abs(H[i] - H[i-j]) for j in range(1, K+1) if i-j >= 0])

# 足場NのインデックスはN-1
print(dp[N-1])

### FIXED CODE ###

import numpy as np

# 入力
N, K = map(int, input().split())
H = np.array([int(i) for i in input().split()])

# ndarray型のDPテーブルを生成
dp = np.zeros(N, dtype=int)
# 初期値をセット
dp[0] = 0

# 各足場へたどり着く最小コストを調べる
for i in range(1, N):
    s = max(0, i-K)
    dp[i] = min(dp[s:i] + np.abs(H[i] - H[s:i])) # iより前の足場のコストに足す

print(dp[N-1])
### BUGGY CODE ###

N = int(input())

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

i=0

while i != N:
    print(A.count(i+1))
    i +=1


### FIXED CODE ###

import collections

N = int(input())

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

c = collections.Counter(A)

for i in range(N):
    print(c[i+1])
### BUGGY CODE ###

###
#Sum of Three Integers
###
k, s = map(int, input().split())
count = 0

for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if (x + y + z) == s:
                count += 1

print(count)

### FIXED CODE ###

###
#Sum of Three Integers
###
k, s = map(int, input().split())
count = 0

for x in range(k + 1):
    for y in range(k + 1):
        z = s - (x + y) 
        if z >= 0 and z <= k:
            count += 1 

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

K = int(input())

P = [n for n in range(1, 10)]
Q = [n for n in range(1, 10)]
for d in range(20):
    if d < 8:
        for m in range(10, 100):
            P.append(int(str(m)+"9"*d))
            Q.append(m//10+m%10+9*d)
    else:
        for m in range(100, 1000):
            P.append(int(str(m)+"9"*(d-1)))
            Q.append(sum([int(s) for s in str(m)])+9*(d-1))

L = len(P)
c = 0
for i, (p, q) in enumerate(zip(P, Q)):
    ok = True
    for j in range(i+1, L):
        np, nq = P[j], Q[j]
        if np*q < nq*p:
            ok = False
            break
    if ok:
        print(p)
        c += 1
    if c == K:
        break


"""
import matplotlib.pyplot as plt

A = []
B = []
for n in range(-1+10**10, 10**15, 10**10):
    m = sum([int(s) for s in str(n)])
    A.append(n)
    B.append(n/m)


plt.plot(A, B)
plt.show()
"""

### FIXED CODE ###

K = int(input())

P = [n for n in range(1, 10)]
Q = [n for n in range(1, 10)]
for d in range(20):
    if d < 12:
        for m in range(10, 100):
            P.append(int(str(m)+"9"*d))
            Q.append(m//10+m%10+9*d)
    else:
        for m in range(100, 1000):
            P.append(int(str(m)+"9"*(d-1)))
            Q.append(sum([int(s) for s in str(m)])+9*(d-1))

L = len(P)
c = 0
for i, (p, q) in enumerate(zip(P, Q)):
    ok = True
    for j in range(i+1, L):
        np, nq = P[j], Q[j]
        if np*q < nq*p:
            ok = False
            break
    if ok:
        print(p)
        c += 1
    if c == K:
        break


"""
import matplotlib.pyplot as plt

A = []
B = []
for n in range(-1+10**10, 10**14, 10**10):
    m = sum([int(s) for s in str(n)])
    A.append(n)
    B.append(n/m)


plt.plot(A, B)
plt.show()
"""
### BUGGY CODE ###

import Queue, math
while True:
    l = 0; r = []
    try:
        inp = map(int, raw_input().split())
        l = inp[0]
        r = inp[1:]
    except EOFError:
        break
    n = len(r)
    if 2*sum(r) <= l:
        print "OK"
    else:
        n2 = 2**n-1
        que = Queue.PriorityQueue()
        dp = [[1000.0 for i in xrange(n)] for j in xrange(2**n)]
        que.put((0.0, 0, -1))
        ok = False
        while not ok and not que.empty():
            co, state, last = que.get()
            if last!=-1 and dp[state][last] < co:
                continue
            for i in xrange(n):
                if (state & (1<<i))==0:
                    nxt = co + math.sqrt(r[last]*r[i])*2.0 if last!=-1 else r[i]
                    nst = state | (1<<i)
                    if nxt + r[i] < l+0.000000001 and nxt < dp[nst][i]:
                        if nst==n2:
                            ok = True
                            break
                        dp[nst][i] = nxt
                        que.put((nxt, nst, i))
        print "OK" if ok else "NA"

### FIXED CODE ###

import math
while True:
    l = 0; r = []
    try:
        inp = map(int, raw_input().split())
        l = inp[0]
        r = inp[1:]
    except EOFError:
        break
    n = len(r)
    if 2*sum(r) <= l:
        print "OK"
    else:
        s = []
        if n>1:
            r.sort()
            for i in xrange(n/2):
                s = [r[i]] + s[::-1] + [r[-i-1]]
            if n&1:
                if abs(s[0]-r[n/2]) < abs(s[-1]-r[n/2]):
                    s.append(r[n/2])
                else:
                    s = [r[n/2]] + s
        else:
            s = r
        ans = s[0] + s[-1]
        for i in xrange(n-1):
            ans += 2*math.sqrt(s[i]*s[i+1])
        print "OK" if ans < 0.000000001+l else "NA"
### BUGGY CODE ###

NUM_LETTER = 26

def solve():
    s = list(raw_input())
    t = list(raw_input())
    Ns = len(s)
    # Create charDict
    charDict = [[] for i in range(NUM_LETTER)]
    for i in range(Ns):
        charDict[ord(s[i]) - ord('a')].append(i)
    # print charDict
    # Search
    ret = 0
    pk_1 = -1
    for i in range(len(t)):
        hashCharDict = ord(t[i]) - ord('a')
        # print "hashCharDict: " + str(hashCharDict)
        if len(charDict[hashCharDict]) == 0:
            ret = -1
            break
        else:
            ind = 0
            while charDict[hashCharDict][ind] <= pk_1:
                ind += 1
                if ind >= len(charDict[hashCharDict]):
                    break
            if ind >= len(charDict[hashCharDict]):
                ret += Ns - pk_1
                pk_1 = charDict[hashCharDict][0]
                ret += pk_1
                # ret = ((ret + 1) // Ns + 1) * Ns + pk_1
            else:
                ret += charDict[hashCharDict][ind] - pk_1
                pk_1 = charDict[hashCharDict][ind]
                # ret = ((ret + 1) // Ns) * Ns + pk_1
        # print "ret: " + str(ret)
    print ret

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import bisect

NUM_LETTER = 26

def solve():
    s = list(raw_input())
    t = list(raw_input())
    Ns = len(s)
    # Create charDict
    charDict = [[] for i in range(NUM_LETTER)]
    for i in range(Ns):
        charDict[ord(s[i]) - ord('a')].append(i)
    # print charDict
    # Search
    ret = 0
    pk_1 = -1
    for i in range(len(t)):
        hashCharDict = ord(t[i]) - ord('a')
        # print "hashCharDict: " + str(hashCharDict)
        if len(charDict[hashCharDict]) == 0:
            ret = -1
            break
        else:
            ind = bisect.bisect(charDict[hashCharDict], pk_1)
            if ind == len(charDict[hashCharDict]):
                ret += Ns - pk_1
                pk_1 = charDict[hashCharDict][0]
                ret += pk_1
            else:
                ret += charDict[hashCharDict][ind] - pk_1
                pk_1 = charDict[hashCharDict][ind]
        # print "ret: " + str(ret)
    print ret

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

n = int(input())
a = list(map(int, input().split()))
count_dict = {}
total_sum = 0
for i in a:
    if i not in count_dict:
        count_dict[i] = a.count(i)
        total_sum += (count_dict[i])*(count_dict[i]-1)//2
for i in a:
    print(total_sum - (count_dict[i]*(count_dict[i]-1)//2) + (count_dict[i]-1)*(count_dict[i]-2)//2)

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
cnt = collections.Counter(a)
total = 0
for key in cnt.keys():
    total += cnt[key]*(cnt[key]-1) // 2
for i in a:
    ans = total
    ans -= cnt[i] * (cnt[i]-1) / 2
    ans += (cnt[i]-1) * (cnt[i]-2) / 2
    print(int(ans))
### BUGGY CODE ###

#!/usr/bin/env python3
N, x = map(int, input().split())
if 1 < x < 2 * N - 1:
    print('Yes')
    l = list(range(1, 2 * N))
    for i in range(2 * N - 1):
        order = (1, -1)[x > N]
        print(l[::order][i - abs(x - N)])
else:
    print('No')


### FIXED CODE ###

#!/usr/bin/env python3
N, x = map(int, input().split())
if 1 < x < 2 * N - 1:
    print('Yes')
    order = (1, -1)[x > N]
    l = list(range(1, 2 * N)[::order])
    for i in range(2 * N - 1):
        print(l[i - abs(x - N)])
else:
    print('No')
### BUGGY CODE ###

N,T = map(int,input().split())
import bisect
C = []
for i in range(N):
    a,b = map(int,input().split())
    index = bisect.bisect_left(C,[a,b])
    C.insert(index,[a,b])
C = sorted(C)
dp = [[0 for i in range(T)]for j in range(N+1)]
for i in range(1,N+1):
    a,b = C[i-1][0],C[i-1][1]
    for t in range(1,T):
        p = dp[i-1][t]
        if t >= a:
            q = dp[i-1][t-a] + b
            dp[i][t] = max(p,q)
        else:
            dp[i][t] = p
M = 0
for i in range(1,N+1):
    M = max(M,C[i-1][1]+dp[i-1][T-1])
print(M)

### FIXED CODE ###

N,T = map(int,input().split())
C = []
for i in range(N):
    a,b = map(int,input().split())
    C.append([a,b])
C.sort()
dp = [[0 for i in range(T)]for j in range(N+1)]
for i in range(1,N+1):
    a,b = C[i-1][0],C[i-1][1]
    for t in range(1,T):
        p = dp[i-1][t]
        if t >= a:
            q = dp[i-1][t-a] + b
            dp[i][t] = max(p,q)
        else:
            dp[i][t] = p
M = 0
for i in range(1,N+1):
    M = max(M,C[i-1][1]+dp[i-1][T-1])
print(M)
### BUGGY CODE ###

n,k = map(int,input().split())
p = [int(i) for i in input().split()]
q = []
for i in range(n):
    q.append((p[i] + 1) / 2)

ans = 0
for i in range(k - 1, n):
    tmp = 0
    for j in range(k):
        tmp += q[i - j]
    ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

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

a = sum(p[0:k])
m = a
o = 0
for i in range(n - k):
    a += p[i + k] - p[i]
    #print(i, p[i + k], p[i], a)
    if a > m:
        m = a
        o = i + 1
'''
q = []
for i in range(n):
    q.append((p[i] + 1) / 2)
'''
ans = 0
#for i in range(k - 1, n):
#tmp = 0
for j in range(o, o + k):
    ans += (p[j] + 1) / 2

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

N,Q=map(int,input().split())
S=input()

lis = []
for i in range(len(S)-1):
  if S[i] == 'A' and S[i+1] == 'C':
    lis += [i]

for _ in range(Q):
  L = tuple(map(int, input().split()))

  c = 0
  for l in lis:
    if L[0] - 1 <= l < L[1] - 1:
      c+=1
      
  
  print(c)


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()

lis = [0] * len(S)
for i in range(len(S)):

  if i>0:
    lis[i] += lis[i-1]
  if i < len(S)-1 and S[i] == 'A' and S[i+1] == 'C':
    lis[i+1] += 1


for _ in range(Q):
  L = tuple(map(int, input().split()))

  c = 0
  print(lis[L[1]-1]-lis[L[0]-1])
### BUGGY CODE ###

# coding: utf-8
# Your code here!

N,K,Q=map(int,input().split())
A=[int(input())-1 for i in range(Q)]

for j in range(N):
    if K-Q+A.count(j)>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
 
P = [0] * N
for i in range(Q):
    tmp = int(input()) - 1
    P[tmp] += 1
 
sumP = sum(P)
for n in range(N):
    ans = 'No'
    total = sumP - P[n]
    if  K - total > 0:
        ans = 'Yes'
    print(ans)
### BUGGY CODE ###

N=int(input())

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

num=[0]*(N+1) #それぞれの数の個数

cnb=[0]*(N+1) #それぞれの球を抜いた時のコンビネーション

for i in range(len(ball)):
  num[ball[i]]+=1


for j in ball:
  
  if cnb[j]==0:
    num[j]-=1

    for k in range(1,len(num)):
      n=num[k]
      if n>=2:
        cnb[j]+=int(n*(n-1)/2)

    print(cnb[j])
    num[j]+=1
  else:
    print(cnb[j])

### FIXED CODE ###

N=int(input())

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

num=[0]*(N+1) #それぞれの数の個数

cnb=[-1]*(N+1) #それぞれの球を抜いた時のコンビネーション

for i in range(len(ball)):
  num[ball[i]]+=1


allcnb=0
for i in num:
  if i>=2:
    allcnb+=int(i*(i-1)/2)

for i in ball:
  cnb=0

  if num[i]>=2:
    cnb=num[i]-1

  print(allcnb-cnb)
### BUGGY CODE ###

x,y = map(int,input().split())

if x == y:
     print('-1')
else:
     i = 2 
     while True:
          if x*i % y == 0:
               i += 1     
               continue
          else:
               print(x*i)
               break 


### FIXED CODE ###

x,y = map(int,input().split())


if x%y == 0:
     print('-1')
else:
     i = 2 
     while True:
          if x*i % y == 0:
               i += 1     
               continue
          else:
               print(x*i)
               break
### BUGGY CODE ###

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

list =[]
for x in range(n+1) :
    k = int(a*x/b) - a* int(x/b)
    list.append(k)
    x += 1
print(max(list))

### FIXED CODE ###

a,b,n = map(int, input().split())
x = min(b-1,n)
print(int(a*x/b))
### BUGGY CODE ###

import itertools

def find(table, x):
    while table[x] != x:
        x = table[x]
    return x

def union(table, x1, x2):
    p1 = find(table, x1)
    p2 = find(table, x2)
    table[p2] = p1

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

edges = []
for j in (0, 1):
    cities1, cities2 = itertools.tee(sorted(range(n), key=lambda city: points[city][j]), 2)
    for city1, city2 in zip(cities1, itertools.islice(cities2, 1, None)):
        (x1, y1), (x2, y2) = points[city1], points[city2]
        cost = min(abs(x1 - x2), abs(y1 - y2))
        edges.append((cost, city1, city2))
edges.sort() # key=lambda cost, city1, city2: cost

table = list(range(n))
answer = 0
for cost, city1, city2 in edges:
    parent1, parent2 = find(table, city1), find(table, city2)
    if parent1 != parent2:
        answer += cost
        union(table, city1, city2)

print(answer)

### FIXED CODE ###

import itertools

def find(table, x):
    stack = [x]
    while table[stack[-1]] != stack[-1]:
        stack.append(table[stack[-1]])
    
    for i in stack:
        table[i] = stack[-1]
    return table[x]


def union(table, x1, x2):
    p1 = find(table, x1)
    p2 = find(table, x2)
    table[p2] = p1

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

edges = []
cities = list(range(n))
for j in (0, 1):
    cities.sort(key=lambda city: points[city][j])
    for i in range(n - 1):
        city1, city2 = cities[i], cities[i + 1]
        (x1, y1), (x2, y2) = points[city1], points[city2]
        cost = min(abs(x1 - x2), abs(y1 - y2))
        edges.append((cost, city1, city2))
edges.sort() # key=lambda cost, city1, city2: cost

table = list(range(n))
answer = 0
for cost, city1, city2 in edges:
    parent1, parent2 = find(table, city1), find(table, city2)
    if parent1 != parent2:
        answer += cost
        union(table, city1, city2)

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

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(w+x+y+z-3for t in zip(a,b,c,d)for w,x,y,z in zip(*t)))
main()

### FIXED CODE ###

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in range(h)for j in range(w)))
main()
### BUGGY CODE ###

N = int(input())
#S = [input() for i in range(N)]
S=[]
firstalpha=[]
ans_list = []
temp_ans = 1
ans = 0

for i in range(N):
    temp = sorted(list(input()))
    S.append(''.join(temp))
    #firstalpha.append(temp[0])
    
set_S = set(S)

for s in set_S:
    a = S.count(s)
    ans += a*(a-1)/2

print(round(ans))

### FIXED CODE ###

N = int(input())
#S = [input() for i in range(N)]
S=[]
ans_dic={}
temp_ans = 1
ans = 0

for i in range(N):
    temp = sorted(list(input()))
    temp = ''.join(temp)
    #S.append(''.join(temp))
    #alpha_dic[temp[0]].append(i) 
    if temp in ans_dic:
        ans_dic[temp] += 1
    else:
        ans_dic[temp] = 1
    
for key,value in ans_dic.items():
    ans += value*(value-1)/2

print(round(ans))