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

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
i = 0
while i < N-2:
    j = i+1
    while j < N-1:
        a = L[i]
        b = L[j]
        if L[j+1] < a+b:
            cOK = j+1
            cNG = N
            while cOK+1<cNG:
                ci = (cOK +cNG)//2
                if L[ci]<a+b:
                    cOK = ci
                else:
                    cNG = ci
            ans += cOK-j
        j += 1
    i += 1

print(ans)

### FIXED CODE ###

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

#N=len(sticks)
sticks = sorted(sticks1, reverse=True)
#sticks.sort(reverse = True)
count = 0
jmax = N-2
kmax = N-1
i=0
while i<N-2:
    j= i+1
    while j<jmax+1:
        k=kmax
        while j<k:
            #sticks[i]>sticks[j]>sticks[k]
            if sticks[i]<sticks[j]+sticks[k]:
                count += k-j
                kmax = k
                break
            else:
                k -= 1
                continue
        jmax = kmax-1
        j += 1
    kmax = N-1
    jmax = N-2
    i += 1
      
print(count)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N = I()
A,B = [], []
for n in range(N):
    A.append(LI())
for n in range(N):
    B.append(LI())

"""
一旦赤い点がどの青い点を持てるのかを洗い出す
lenが小さい順に青を消していく。
何個消せるかで勝負
"""

b_a = []
for b in B:
    tmp = []
    for a in A:
        if a[0] < b[0] and a[1] < b[1]:
            # 赤が青より小さいとき
            tmp.append(a)
    if tmp:
        b_a.append(tmp)
#  print(b_a)

result = 0
results = []
def dfs(arr, count):
    for i in range(len(arr)-1, -1, -1):
        arr = sorted(arr, reverse=True, key=lambda x: len(x))
        popped = arr.pop()
        for p in popped:
            popped = p
            tmp = [_ for _ in arr]
            tmp = [[k for k in j if k != popped] for j in tmp]
            tmp = [j for j in tmp if j != []]
            if not tmp:
                results.append(count+1)
            else:
                dfs(tmp, count+1)


dfs(b_a, 0)
#  print(results)
if not results:
    print(0)
    exit()
print(max(results))

		

### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N = I()
A,B = [], []
for n in range(N):
    A.append(LI())
for n in range(N):
    B.append(LI())

#  N = 100
#  A,B = [], []
#  for n in range(N):
#      A.append([random.randint(0,2*N), random.randint(0, 2*N)])
#  for n in range(N):
#      B.append([random.randint(0,2*N), random.randint(0, 2*N)])

B = sorted(B, key=lambda x: x[0])

result = 0
for b in B:
    tmp = [a for a in A if a[0] < b[0] and a[1] < b[1]]
    if not tmp:
        continue
    result += 1
    closest = max(tmp, key=lambda x: x[1])
    A.remove(closest)
print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())

I = [[0]*C for i in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    I[r-1][c-1] = v   # 0-indexed

dp = [[[0 for k in range(4)]
       for j in range(C+1)] for i in range(R+1)]
for i in range(R):
    for j in range(C):
        for k in range(2, -1, -1):
            dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k]+I[i][j])
        for k in range(4):
            dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k])
            dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])


# print(*dp, sep=' \n')

ans = 0
for k in range(4):
    ans = max(ans, dp[R-1][C-1][k])
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())

I = [[0]*C for i in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    I[r-1][c-1] = v   # 0-indexed

dp0 = [[0 for j in range(C+1)] for i in range(R+1)]
dp1 = [[0 for j in range(C+1)] for i in range(R+1)]
dp2 = [[0 for j in range(C+1)] for i in range(R+1)]
dp3 = [[0 for j in range(C+1)] for i in range(R+1)]
for i in range(R):
    for j in range(C):
        dp3[i][j] = max(dp3[i][j], dp2[i][j]+I[i][j])
        dp2[i][j] = max(dp2[i][j], dp1[i][j]+I[i][j])
        dp1[i][j] = max(dp1[i][j], dp0[i][j]+I[i][j])
        dp0[i+1][j] = max(dp0[i+1][j], dp0[i][j], dp1[i]
                          [j], dp2[i][j], dp3[i][j])
        dp0[i][j+1] = max(dp0[i][j+1], dp0[i][j])
        dp1[i][j+1] = max(dp1[i][j+1], dp1[i][j])
        dp2[i][j+1] = max(dp2[i][j+1], dp2[i][j])
        dp3[i][j+1] = max(dp3[i][j+1], dp3[i][j])


# print(*dp, sep=' \n')

ans = max(dp0[R-1][C-1], dp1[R-1][C-1], dp2[R-1][C-1], dp3[R-1][C-1])
print(ans)
### BUGGY CODE ###

import math
import fractions

K = int(input())
sum = 0

def gcd(x,y,z):
    a = [x,y,z]
    ans = a[0]
    for i in range(1,len(a)):
        ans = math.gcd(ans,a[i])
    return ans

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            sum += gcd(i,j,k)


print(sum)


"""
import fractions
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = fractions.gcd(ans, a[i])
print(ans)
"""

### FIXED CODE ###

import math
import fractions

K = int(input())
sum = 0

def gcd2(x,y,z):
    return math.gcd(math.gcd(x,y),z)

for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            if (i == j == k):
                sum += gcd2(i,j,k)
            elif i != j and j != k:
                sum += gcd2(i,j,k)*6
            else:
                sum += gcd2(i,j,k)*3



print(sum)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

N,M = map(int,input().split())
L,R = map(int,input().split())
curSet = set(range(L,R+1))

for i in range(2,M+1):
    L,R = map(int,input().split())
    curVec = set(range(L,R+1))

    curSet = curSet.intersection(curVec)
    
print(len(curSet))

### FIXED CODE ###

# coding: utf-8
# Your code here!

N,M = map(int,input().split())
L = [0]*M
R = [0]*M
#Li,Ri = map(int,input().split())

for i in range(1,M+1):
    L[i-1],R[i-1] = map(int,input().split())

validID = min(R)-max(L)+1

if (validID>0):
    print(validID)
else:
    print("0")
### BUGGY CODE ###

import sys
input=sys.stdin.readline
class BinaryIndexedTree():
  def __init__(self,n):self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_1(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_1(j-1)
    if i!=0:a-=self.sum_1(i-1)
    return a
def tentousu(a):
  bit=BinaryIndexedTree(n)
  b=[0]*n
  for i in range(n):
    b[a[i]]=i
  ans=0
  for i in range(n):
    j=b[i]+bit.sum(b[i]+1,n)
    ans+=j-i
    bit.add(b[i],1)
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
import itertools
xx=[i for i in range(n)]
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in itertools.combinations(xx,(n+1)//2):
  s=set(i)
  ac=[]
  bc=[]
  for j in range(n):
    if j in s:ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)

### FIXED CODE ###

class BinaryIndexedTree():
  def __init__(self,n):self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_1(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_1(j-1)
    if i!=0:a-=self.sum_1(i-1)
    return a
def tentousu(a):
  bit=BinaryIndexedTree(n)
  b=[0]*n
  for i in range(n):
    b[a[i]]=i
  ans=0
  for i in range(n):
    j=b[i]+bit.sum(b[i]+1,n)
    ans+=j-i
    bit.add(b[i],1)
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  if s.count("0")!=n//2:continue
  ac=[]
  bc=[]
  for j in range(n):
    if s[j]=="1":ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)
### BUGGY CODE ###

N = int(input())
final_ans = 1
for h in range(2,N):
         n = h
         x = n
         ans = []
         for i in range(2,int(x**(1/2))+1):
                  if n % i == 0:
                           soinsuu = i
                           zyousuu = 0
                           while n % i == 0:
                                    n = n // i
                                    zyousuu += 1
                           ans.append([soinsuu,zyousuu])
         if n != 1:
                  ans.append([n,1])
         tmp = 1
         for j in range(len(ans)):
                  tmp *= (ans[j][1] + 1)
         final_ans += tmp
print(final_ans)
                  
                  


### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n):
         ans += ((n-1) // i)
print(ans)
### BUGGY CODE ###

n=int(input())
s=list(input())
r=[i for i, x in enumerate(s) if x == 'R']
g=[i for i, x in enumerate(s) if x == 'G']
b=[i for i, x in enumerate(s) if x == 'B']
R,G,B=len(r),len(g),len(b)
ans=0
for i in range(R):
    for j in range(G):
        for k in range(B):
            l=sorted([r[i],g[j],b[k]])
            ans+=1 if l[1]-l[0]!=l[2]-l[1]  else 0
print(ans)

### FIXED CODE ###

def main():
  n=int(input())
  s=input()
  R,G,B=s.count('R'),s.count('G'),s.count('B')
  ans=R*G*B
  for i in range(n):
    for j in range(i+1,n):
      if 2*j-i>n-1:
        break
      if s[i]!=s[j] and s[j]!=s[2*j-i] and s[2*j-i]!=s[i]:
        ans-=1
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

S=input()

ans = 0
for i in range(len(S)):
    for j in range(i+4,len(S)+1):
        if int(S[i:j]) % 2019 == 0:
            ans+=1

print(ans)



### FIXED CODE ###

from collections import defaultdict
 
 
def solve2(s):
    ans = 0
    for i, c in enumerate(s):
        if c in '02468':
            ans += i + 1
    return ans
 
 
def solve5(s):
    ans = 0
    for i, c in enumerate(s):
        if c in '05':
            ans += i + 1
    return ans
 
 
def solve_other(s, p):
    reminders = defaultdict(lambda: 0)
    tmp = 0
    mul = 1
    for c in s[::-1]:
        c = int(c)
        tmp = (tmp + c * mul) % p
        mul = mul * 10 % p
        reminders[tmp] += 1
    reminders[0] += 1
    ans = 0
    for r, cnt in reminders.items():
        ans += cnt * (cnt - 1) // 2
    return ans
 
 

s = input()
n = len(s)
p = 2019


if p == 2:
    print(solve2(s))
elif p == 5:
    print(solve5(s))
else:
    print(solve_other(s, p))
### BUGGY CODE ###

n, q = [int(el) for el in input().split(' ')]
data = [0] * n
ex_result = 0
ex_index = 0
for _ in range(q):
    a, v = [int(el) for el in input().split(' ')]
    data[a-1] += v
    if ex_index != a:
        if v < 0: result = ex_result
        else: result = max(ex_result, data[a-1])
    elif ex_index == a:
        if v > 0: result = data[a-1]
        else: result = max(data)
    index = data.index(result)+1
    print(index, result)
    ex_result = result
    ex_index = index

### FIXED CODE ###

n, q = [int(el) for el in input().split(' ')]
data = [0] * n
result, index = 0, 1
for _ in range(q):
    a, v = [int(el) for el in input().split(' ')]
    data[a-1] += v
    if v > 0:
        if result < data[a-1]:
            result, index = data[a-1], a
        elif result == data[a-1]:
            index = min(index, a)
    else:
        if index == a:
            result = max(data)
            index = data.index(result) + 1
    print(index, result)
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)

n=int(input())
dct=defaultdict(list)

for i in range(n-1):
  a,b,c=map(int,input().split())
  dct[a]+=[[b,c]]
  dct[b]+=[[a,c]]


q,k=map(int,input().split())
lk=[0]*(n)

def dfs(v,p,d):
  lk[v-1]=d

  for l in dct[v]:
    if l[0]==p or lk[l[0]-1]!=0:
      continue
    else:
      dfs(l[0],v,d+l[1])
  return

dfs(k,-1,0)



for i in range(q):
  x,y=map(int,input().split())
  print(lk[x-1]+lk[y-1])


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)

n=int(input())
dct=defaultdict(list)

for i in range(n-1):
  a,b,c=map(int,input().split())
  dct[a]+=[[b,c]]
  dct[b]+=[[a,c]]


q,k=map(int,input().split())
lk=[0]*(n)

def dfs(v,p,d):
  lk[v-1]=d

  for l in dct[v]:
    if l[0]==p or lk[l[0]-1]!=0:
      continue
    else:
      dfs(l[0],v,d+l[1])
  return

dfs(k,-1,0)



for i in range(q):
  x,y=map(int,input().split())
  print(lk[x-1]+lk[y-1])
### BUGGY CODE ###

K=int(input())
S=input()

len_S=len(S)

#逆元を用いたコンビネーション
mod = 10**9+7
def mul_mod(a,b):
  return (a*b) % mod

def fact_inv(a):
  ans = 1
  for i in range(1,a+1):
    ans = (pow(i,mod-2,mod) * ans) % mod
  return ans

fact_list = [1]
for i in range(1,len_S+K):
  fact_list.append(mul_mod(fact_list[-1],i))

fact_list_inv = [1]
for i in range(1,len_S+K):
  fact_list_inv .append((pow(i,mod-2,mod) * fact_list_inv[-1]) % mod)

def comb_inv_mod(a,b):
  return (fact_list[a]*fact_list_inv[b]*fact_list_inv[a-b]) % mod

ans = 0
for i in range(len_S-1,len_S+K): #Snの位置
  #print(i)
  #ans += comb_inv(len_S+K-(len_S+K-i-1)-1,N-1)*pow(25,(K-(len_S+K-i-1)),mod)*pow(26,len_S+K-i-1,mod)
  A = comb_inv_mod(i,len_S-1)*pow(25,i-len_S+1,mod) % mod 
  A = A*pow(26,len_S+K-i-1,mod) % mod
  ans += A
  #print(ans)
  ans = ans % mod
print(ans)

### FIXED CODE ###

K=int(input())
S=input()

len_S=len(S)

#逆元を用いたコンビネーション
mod = 10**9+7
def mul_mod(a,b):
  return (a*b) % mod

def fact_inv(a):
  ans = 1
  for i in range(1,a+1):
    ans = (pow(i,mod-2,mod) * ans) % mod
  return ans

fact_list = [1]
for i in range(1,len_S+K):
  fact_list.append(mul_mod(fact_list[-1],i))

fact_list_inv = [1]
for i in range(1,len_S+K):
  fact_list_inv .append((pow(i,mod-2,mod) * fact_list_inv[-1]) % mod)
def comb_inv_mod(a,b):
  tmp = (fact_list[a]*fact_list_inv[b]) % mod
  return (tmp*fact_list_inv[a-b]) % mod

ans = 0
for i in range(len_S-1,len_S+K): #Snの位置
  #print(i)
  #ans += comb_inv(len_S+K-(len_S+K-i-1)-1,N-1)*pow(25,(K-(len_S+K-i-1)),mod)*pow(26,len_S+K-i-1,mod)
  A = comb_inv_mod(i,len_S-1)*pow(25,i-len_S+1,mod) % mod 
  A = A*pow(26,len_S+K-i-1,mod) % mod
  ans += A
  #print(ans)
  ans = ans % mod
print(ans)
### BUGGY CODE ###

h,w = list(map(int, input().split()))
# 初期位置
ch,cw = list(map(int, input().split()))
# ゴール位置
dh,dw = list(map(int, input().split()))
b = [['#']*(w+2)]
for _ in range(h):
    b.append(['#'] + list(input()) + ['#'])
b.append(['#']*(w+2))

from collections import deque
q = deque()
nq = deque()
q.append((ch, cw))

visit = [[False]*(w+2) for _ in range(h+2)]

warp = 0
while q or nq:
    while q:
        y,x = q.popleft()
        if (y,x) == (dh,dw):
            print(warp)
            exit()
        if visit[y][x]:
            continue
        visit[y][x] = True
        for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
            if b[y+dy][x+dx] == '.':
                if not visit[y+dy][x+dx] and (y+dy, x+dx) not in q:
                    q.append((y+dy, x+dx))
            else:
                for dx in (-2,-1,0,1,2):
                    for dy in (-2,-1,0,1,2):
                        if y+dy > h or x + dx > w:
                            continue
                        if b[y+dy][x+dx] == '.':
                            if not visit[y+dy][x+dx] and (y+dy, x+dx) not in nq:
                                nq.append((y+dy, x+dx))
    q = nq
    nq = deque()
    warp += 1
    
print(-1)

### FIXED CODE ###

h,w = list(map(int, input().split()))
# 初期位置
ch,cw = list(map(int, input().split()))
# ゴール位置
dh,dw = list(map(int, input().split()))
b = [['#']*(w+2)]
for _ in range(h):
    b.append(['#'] + list(input()) + ['#'])
b.append(['#']*(w+2))

from collections import deque
q = deque()
nq = deque()
q.append((ch, cw))

visit = [[False]*(w+2) for _ in range(h+2)]

warp = 0
while q or nq:
    while q:
        y,x = q.popleft()
        if (y,x) == (dh,dw):
            print(warp)
            exit()
        if visit[y][x]:
            continue
        visit[y][x] = True
        for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
            if b[y+dy][x+dx] == '.':
                if not visit[y+dy][x+dx]:
                    q.append((y+dy, x+dx))
            else:
                for dx in (-2,-1,0,1,2):
                    for dy in (-2,-1,0,1,2):
                        if y+dy > h or x + dx > w:
                            continue
                        if b[y+dy][x+dx] == '.':
                            if not visit[y+dy][x+dx]:
                                nq.append((y+dy, x+dx))
    q = nq
    nq = deque()
    warp += 1
    
print(-1)
### BUGGY CODE ###

# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, A, B, K = lr()
answer = 0
# A * x + B * y = K
# nCx * nCy



def cmb(n, k):
    if k < 0 or k > n: return 0 
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 6 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

for x in range(N+1):
    temp = K-A*x
    if temp%B != 0:
        continue
    y = temp // B
    if y > N:
        continue
    if y < 0:
        break
    answer += cmb(N, x) * cmb(N, y)
    answer %= MOD

print(answer % MOD)


### FIXED CODE ###

# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, A, B, K = lr()
answer = 0
# A * x + B * y = K
# nCx * nCy

def cmb(n, k):
    if k < 0 or k > n: return 0 
    return fact_N * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = N + 100 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
fact_N = fact[N]

for x in range(N+1):
    temp = K-A*x
    if temp%B != 0:
        continue
    y = temp // B
    if y > N:
        continue
    if y < 0:
        break
    answer += cmb(N, x) * cmb(N, y)
    answer %= MOD

print(answer % MOD)
### BUGGY CODE ###

from collections import Counter

n = int(input())
s = []

for i in range(n):
  c = Counter(input())
  s.append(c)

result = 0

for i in range(n):
  for j in range(i+1, n):
    if s[i] == s[j]:
      result += 1

print(result)


### FIXED CODE ###

n = int(input())
s = {}

for i in range(n):
  #c = "{}".format(sorted(Counter(input()).most_common()))
  c = "".join(sorted(input()))
  v = s.get(c, 0)
  s[c] = v + 1

result = 0

for v in s.values():
  result += v * (v-1) / 2

print(int(result))
### BUGGY CODE ###

print(sum(range(int(input()))))

### FIXED CODE ###

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

import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
node = [0] * n
to = [[] for _ in range(n)]
ans = [-1] * n
for _ in range(n-1):
    a, b = map(int, input().split())
    to[b-1].append(a-1)
    to[a-1].append(b-1)
for _ in range(q):
    p, x = map(int, input().split())
    node[p-1]+=x

def dfs(i, source, count=0):
    node[i]+=count
    for next_node in to[i]:
        if next_node == source: continue 
        dfs(next_node, i, node[i])
dfs(0, -1, 0)

print(' '.join(list(map(str, node))))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
node = [0] * n
to = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    to[b-1].append(a-1)
    to[a-1].append(b-1)
for _ in range(q):
    p, x = map(int, input().split())
    node[p-1]+=x

def dfs(i, source, count=0):
    node[i]+=count
    for next_node in to[i]:
        if next_node == source: continue 
        dfs(next_node, i, node[i])
dfs(0, -1, 0)

print(' '.join(list(map(str, node))))
### BUGGY CODE ###

def main() :
    a = input()
    L = len(a)
    ans = 1
    for i in range(L-1) :
        for j in range(L-1, i, -1) :
            if a[i] != a[j] :
                ans += 1

    print(ans)

main()

### FIXED CODE ###

def main() :
    a = input()
    L = len(a)
    ans = L*(L-1)//2 + 1
    alp = "abcdefghijklmnopqrstuvwxyz"

    for c in alp :
        cnt = a.count(c)
        ans -= cnt*(cnt-1)//2
    
    print(ans)

main()