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

def main():
  from collections import deque
  import sys
  input=sys.stdin.readline
  calc=lambda x,y:x*1000007+y
  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))
  d=deque()
  d.append(calc(sx,sy))
  s=set()
  while d:
    x,y=divmod(d.popleft(),1000007)
    if calc(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(calc(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(calc(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(calc(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(calc(x,y+j))
      if b[x][y+j]!=0:
        s.add((x,y+j))
      b[x][y+j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()


### 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 math
import sys
import itertools
from math import gcd
from math import sqrt
from sys import stdin
def input() : return stdin.readline().rstrip()
def mips():
    return map(int,input().split())
def ii():
    return int(input())
sys.setrecursionlimit(10**9)

N,M,K = mips()
A = [i for i in mips()]
B = [i for i in mips()]
# N,M <= 200000
ans = 0
clock = K
A2 = [0]
B2 = [0]
for i in range(1,N+1):
    ai = A2[i-1] + A[i-1]
    A2.append(ai)
for i in range(1,M+1):
    bi = B2[i-1] + B[i-1]
    B2.append(bi)
for i in range(N+1):
    j = M
    while (j >= 0):
        if A2[i] + B2[j] <= K:
            ans = max(ans,i+j)
        j -= 1
print(ans)

### FIXED CODE ###

import math
import sys
import itertools
from math import gcd
from math import sqrt
from sys import stdin
def input() : return stdin.readline().rstrip()
def mips():
    return map(int,input().split())
def ii():
    return int(input())
sys.setrecursionlimit(10**9)

N,M,K = mips()
A = [i for i in mips()]
B = [i for i in mips()]
# N,M <= 200000
ans = 0
clock = K
A2 = [0]
B2 = [0]
for i in range(1,N+1):
    ai = A2[i-1] + A[i-1]
    A2.append(ai)
for i in range(1,M+1):
    bi = B2[i-1] + B[i-1]
    B2.append(bi)
j = M
for i in range(N+1):
    if A2[i] > K:
        break
    while (B2[j] + A2[i] > K):
        j -= 1
    ans = max(ans,i+j)
print(ans)
### BUGGY CODE ###

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

ans = 1
for num in nums:
    ans = ans * num

if ans > 10**18:
    print('-1')
else:
    print(ans)


### FIXED CODE ###

N = int(input())
nums = sorted(map(int, input().split()))
if nums[0] == 0:
    print(0)
else:
    ans = 1
    for num in nums:
        ans = ans * num
        if ans > 10**18:
            break
    if ans > 10**18:
        print('-1')
    else:
        print(ans)
### BUGGY CODE ###

import heapq

ceil = lambda a, b: (a + b - 1) // b

N, K = map(int, input().split())
A = tuple(map(int, input().split()))

h = [(-a, a, 1) for a in A]
heapq.heapify(h)
for _ in range(K):
    l, a, ct = heapq.heappop(h)
    ct += 1
    heapq.heappush(h, (-a / ct, a, ct))
_, a, ct = heapq.heappop(h)
print(ceil(a, ct))


### FIXED CODE ###

ceil = lambda a, b: (a + b - 1) // b

N, K = map(int, input().split())
A = tuple(map(int, input().split()))

# bisect
l, r = 0, max(A)
while r - l > 1:
    m = (l + r) // 2
    if sum(ceil(x, m) - 1 for x in A) > K:
        l = m
    else:
        r = m
print(r)
### BUGGY CODE ###

n,m=map(int,input().split())
s=input()
a=[]
b=len(s)
c=0
d=n
e=0
while d>0:
  if d<=m:
    a.insert(0,d)
    d=0
  else:
    i=m
    while i>0:
      if s[d-i]=="1":
        i=i-1
      else:
        a.insert(0,i)
        d=d-i
        i=-1
    if i==0:
        e=1
        break
    else:
      continue
    break
if e==1:
  print(-1)
else:
  for i in range(len(a)):
    print(a[i],end=" ")

### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
s=deque(input())
a=0
for i in range(n+1):
  if s[i]=="1":
    a=a+1
    if a==m:
      print(-1)
      break
  else:
    a=0
if a==0:
  b=deque([])
  d=n
  while d>0:
    if d<=m:
      b.appendleft(d)
      d=0
    else:
      i=m
      while i>0:
        if s[d-i]=="1":
          i=i-1
        else:
          b.appendleft(i)
          d=d-i
          for j in range(i):
            s.pop()
          break
  for i in range(len(b)):
    print(b[i],end=" ")
### BUGGY CODE ###

k = int(input())
m = 7
if(k%2==0):
  print("-1")
else:
  i = 1
  while True:
    if(m%k==0):
      print(i)
      break  
    if(i>1000000):
      print("-1")
      break
    m *= 10
    m += 7
    i += 1


### FIXED CODE ###

k = int(input())
m = 7
if(k%2==0):
  print("-1")
else:
  i = 1
  while True:
    m = m%k
    if(m==0):
      print(i)
      break  
    if(i>k):
      print("-1")
      break
    m *= 10
    m += 7
    i += 1
### BUGGY CODE ###

n = int(input())
s = list(input())

def check(pin):
    i = 0
    pi = 0
    while i<n and pi<3:
        if s[i]==pin[pi]:
            pi += 1
        i += 1
    return pi==3

res = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            if check(str(i)+str(j)+str(k)):
                res += 1

print(res)

### FIXED CODE ###

n = int(input())
s = list(input())

d = [[] for _ in range(10)]
for i in range(n):
    d[int(s[i])].append(i)

def lower_bound(al,k):
    if len(al)==0:
        return -1
    ng = -1
    ok = len(al)
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if al[mid]>k:
            ok = mid
        else:
            ng = mid
    if ok==len(al):
        return -1
    return ok

def check(pl):
    pos = -1
    res = []
    for i in range(3):
        pos = lower_bound(d[pl[i]], pos)
        if pos<0:
            return False
        pos = d[pl[i]][pos]
        res.append(pos)
    return True

res = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            if check([i,j,k]):
                res += 1

print(res)
### BUGGY CODE ###

n = int(input())
a =list(map(int,input().split()))
total = 1
i = 0
while i <n:
    if 0 in a:
        total =0 
        break
    
    total *= int(a[i])
    if total >10**18:
        total = '-1'
        break
    i += 1
    
print(total)

### FIXED CODE ###

a = int(input())
li = list(map(int,input().split()))
total = 1
i = 1
for i in range(a):
    total = total*li[i]
    if total > 1000000000000000000:
        total = -1
        break
for i in range(a):
    if li[i] == 0:
        total = 0
 
print(total)
### BUGGY CODE ###

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

for i in range(1,n+1):
    if k - (q - a.count(i)) > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k,q = list(map(int,input().split()))
a = [int(input()) for i in range(q)]
np = [0]*n

for i in range(q):
    np[a[i]-1] += 1

for i in range(n):
    if k- (q - np[i]) >= 1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans =1;
iszero = False

if 0 in A:
  iszero = True

for i in range(N):
  if(iszero):
    ans = 0
    break
    
  ans *= A[i]
  
  if ans>10**18:
    ans = -1

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans =1;
iszero = False

if 0 in A:
  iszero = True
for i in range(N):
  if(iszero):
    ans = 0
    break
  ans *= A[i] 
  if ans>10**18:
    ans = -1
    break

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

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

if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
    print(counter)
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
    print(counter)
else:
    list_a=[0]
    counter=0
    for i in range(len(S)):
        temp=int(S[N-i-1:])%P
        counter+=list_a.count(temp)
        list_a.append(temp)
    print(counter)

### FIXED CODE ###

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

counter=0
def power_func(a,b,p):
    if b==0:
        return 1
    elif b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    elif b%2==1:
        return (a*power_func(a,b-1,p ))%p
if P==2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2','4','6','8','0']:
            counter+=i+1
elif P==5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5','0']:
            counter+=i+1
else:
    list_a=[0]*P
    list_a[0]+=1
    temp=0
    for i in range(N):
        M = power_func(10,N-i,P)
        temp=(int(S[i])*M+temp)%P
        counter+=list_a[temp]
        list_a[temp]+=1
print(counter)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
  print(a.count(i))

### FIXED CODE ###

from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
for i in range(n):
  print(c[i + 1])
### BUGGY CODE ###

from operator import mul
from functools import reduce
n, a, b = map(int, input().split())


def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

print((pow(2, n) - cmb(n, a) - cmb(n, b) - 1) % (pow(10, 9)+7))

### FIXED CODE ###

n, a, b = map(int, input().split())
mod = pow(10, 9) + 7


def cmb(n,r):
    mod = 10**9+7
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    for i in range(1,r+1):
        ans *= pow(i,mod-2,mod)
        ans %= mod
    return ans


total = pow(2, n, mod) - cmb(n, a) - cmb(n, b) - 1
print(total % mod)
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(k)]
mod = 998244353

s.sort()

dp = np.zeros(n * 2)
dp[1] = 1

for i in range(1, n):
    for l, r in s:
        dp[i + l:i + r + 1] += dp[i]
        dp[i + l:i + r + 1] %= mod

ans=int(dp[n] % mod)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
mod = 998244353
lr = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n + 10)
dp[1] = 1
cumsum = [0] * (n + 10)
cumsum[1] = 1

for i in range(2, n + 1):
    for l, r in lr:
        if l >= i:
            continue

        ll = max(1, i - r)
        rr = i - l
        if ll <= rr:
            dp[i] += cumsum[rr] - cumsum[ll - 1]
            dp[i] %= mod
    cumsum[i] = cumsum[i - 1] + dp[i]
    cumsum[i] %= mod

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

N = int(input())
lista = []
for i in range(N):
    lista.append(int(input()))
for i in range(N):
    save = lista[i]
    lista.pop(i)
    print(max(lista))
    lista.insert(i,save)

### FIXED CODE ###

A = int(input())
No1,No2 = 0,0
for i in range(A):
    B = int(input())
    if No2 < B:
        No2 = B
        if No1 < B:
            place = i
        No1,No2 = max(No1,No2),min(No1,No2)
if No1 == No2:
    for i in range(A):
        print(No1)
else:
    for i in range(place):
        print(No1)
    print(No2)
    for i in range(A-place-1):
        print(No1)
### BUGGY CODE ###

n=int(input())
num=[int(input()) for _ in range(5)]

cnt=0
stay=[0]*5
move=[0]*5
stay[0]=n
while(sum(stay)>0):
    for i in range(5):
        if stay[i]>=num[i]:
            move[i]=num[i]
            stay[i]-=num[i]
        elif stay[i]!=0:
            move[i]=stay[i]
            stay[i]=0
        elif stay[i]==0:
            move[i]=0
    
    for i in range(1,5):
        stay[i]+=move[i-1]
    
    cnt+=1
    
print(cnt)

### FIXED CODE ###

n=int(input())
num=[int(input()) for _ in range(5)]

print(-(-n//min(num))+4)
### BUGGY CODE ###

MOD = 998244353
n, s = map(int, input().split())
a = list(map(int, input().split()))
f = [0] * (s + 1)
f[0] = pow(2, n, MOD)
v = pow(2, MOD - 2, MOD)
for i in range(n):
    for j in range(s, a[i] - 1, -1):
        f[j] += f[j - a[i]] * v
    for j in range(s + 1):
        f[j] %= MOD
print(f[s])


### FIXED CODE ###

MOD = 998244353
n, s = map(int, input().split())
a = list(map(int, input().split()))
f = [0] * (s + 1)
f[0] = pow(2, n, MOD)
v = pow(2, MOD - 2, MOD)
for x in a:
    for j in range(s, x - 1, -1):
        f[j] += f[j - x] * v
    for j in range(s + 1):
        f[j] %= MOD
print(f[s])
### BUGGY CODE ###

a,b,k = map(int,input().split())
ak = a+k
bk = b-k

for i in range(a,b+1):
  if i<ak or i>bk:
    print(i)

### FIXED CODE ###

a,b,k = map(int,input().split())
ak = a+k
bk = b-k

if a+k>=b:
  for i in range(a,b+1):
    if i<ak or i>bk:
      print(i)
else:
  for i in range(a,a+k+1):
    if i<ak or i>bk:
      print(i)
  if i<b-k:
    for n in range(b-k,b+1):
      if n<b-k or n>bk:
        print(n)
  else:
    for j in range(i+1,b+1):
      if j<ak or j>bk:
        print(j)
### BUGGY CODE ###

num_limit = int(input())
s_limit = int(num_limit**0.5)
for i in range(1,num_limit+1):
    xyz_list = []
    s_limit = int(i ** 0.5)
    for j in range(1,s_limit+1):
        for k in range(1,s_limit+1):
            for l in range(1,s_limit+1):
                if i == j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    xyz_list.append([i,j,k])
    print(len(xyz_list))

### FIXED CODE ###

num_limit = int(input())
num_list = [0] * num_limit
j_limit = int(num_limit ** 0.5)
for j in range(1,j_limit+1):
    for k in range(1,j + 1):
        for l in range(1,k+1):
            if num_limit >= j**2 + k**2 + l**2 + j*k + k*l + l*j:
                if j > k:
                    if k > l:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 6
                    else:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                elif k > l:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                else:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 1
for i in num_list:
    print(i)
### BUGGY CODE ###

n, k = [int(x) for x in input().split()]
p = [1/2 + int(x)/2 for x in input().split()]
max_t = 0
for i in range(n - k + 1):
    buf = sum(p[i:i + k])
    if max_t < buf:
        max_t = buf
print(max_t)

### FIXED CODE ###

n, k = [int(x) for x in input().split()]
p = [1/2 + int(x)/2 for x in input().split()]
sum_p =[]
buf = 0
for i in p:
    buf += i
    sum_p.append(buf)
max_t = 0
for i in range(n - k + 1):
    buf = sum_p[i+k-1]
    if i > 0:
        buf -= sum_p[i-1]
    if max_t < buf:
        max_t = buf
print(max_t)
### BUGGY CODE ###

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

if N==1:
    if A[0]==A[1]==A[2]:
        print(1)
    else:
        print(0)
    exit()

INF = float('inf')
ans = 0
dp = [[-INF]*(N+1) for _ in range(N+1)]
dp[A[0]][A[1]] = dp[A[1]][A[0]] = 0
maxdp = [max(row) for row in dp]

for i in range(N-1):
    a,b,c = A[i*3+2:i*3+5]
    if a==b==c:
        ans += 1
        continue
    update = []
    if a==b:
        for j in range(1,N+1):
            update.append((j,c, max(dp[a][j], dp[j][a]) + 1))
    elif b==c:
        for j in range(1,N+1):
            update.append((j,a, max(dp[b][j], dp[j][b]) + 1))
    elif c==a:
        for j in range(1,N+1):
            update.append((j,b, max(dp[c][j], dp[j][c]) + 1))
    update.append((a,b, dp[c][c] + 1))
    update.append((b,c, dp[a][a] + 1))
    update.append((c,a, dp[b][b] + 1))
    mx = max(maxdp)
    update.append((a,b, mx))
    update.append((b,c, mx))
    update.append((c,a, mx))
    for j in range(1,N+1):
        update.append((j,a, maxdp[j]))
        update.append((j,b, maxdp[j]))
        update.append((j,c, maxdp[j]))
    for l,m,n in update:
        dp[l][m] = dp[m][l] = max(dp[l][m], dp[m][l], n)
        maxdp[l] = max(maxdp[l], n)
        maxdp[m] = max(maxdp[m], n)

tmp = max(maxdp)
tmp = max(tmp, dp[A[-1]][A[-1]] + 1)
ans += tmp
print(ans)

### FIXED CODE ###

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

if N==1:
    if A[0]==A[1]==A[2]:
        print(1)
    else:
        print(0)
    exit()

INF = float('inf')
ans = 0
dp = [[-INF]*(N+1) for _ in range(N+1)]
dp[A[0]][A[1]] = dp[A[1]][A[0]] = 0
maxdp = [max(row) for row in dp]
use = {A[0], A[1]}

for i in range(N-1):
    a,b,c = A[i*3+2:i*3+5]
    if a==b==c:
        ans += 1
        continue
    update = []
    if a==b:
        for j in use:
            update.append((j,c, max(dp[a][j], dp[j][a]) + 1))
    elif b==c:
        for j in use:
            update.append((j,a, max(dp[b][j], dp[j][b]) + 1))
    elif c==a:
        for j in use:
            update.append((j,b, max(dp[c][j], dp[j][c]) + 1))
    update.append((a,b, dp[c][c] + 1))
    update.append((b,c, dp[a][a] + 1))
    update.append((c,a, dp[b][b] + 1))
    mx = max(maxdp)
    update.append((a,b, mx))
    update.append((b,c, mx))
    update.append((c,a, mx))
    for j in use:
        update.append((j,a, maxdp[j]))
        update.append((j,b, maxdp[j]))
        update.append((j,c, maxdp[j]))
    for l,m,n in update:
        dp[l][m] = dp[m][l] = max(dp[l][m], dp[m][l], n)
        maxdp[l] = max(maxdp[l], n)
        maxdp[m] = max(maxdp[m], n)
    use.add(a)
    use.add(b)
    use.add(c)

tmp = max(maxdp)
tmp = max(tmp, dp[A[-1]][A[-1]] + 1)
ans += tmp
print(ans)
### BUGGY CODE ###

n,p=map(int,input().split())
arr=[]
arr1=[]
for i in range(100001):
    arr1.append([])
for i in range(p):
    arr.append(list(map(int,input().split())))
    arr1[arr[i][0]].append(arr[i][1])
for i in range(len(arr1)):
    arr1[i].sort()
for i in range(p):
    print("%06d%06d"%(arr[i][0],arr1[arr[i][0]].index(arr[i][1])+1))

### FIXED CODE ###

import bisect
n,p=map(int,input().split())
arr=[]
arr1=[[] for i in range(100001)]
for i in range(p):
    arr.append(list(map(int,input().split())))
    arr1[arr[i][0]].append(arr[i][1])
for i in range(100001):
    if(len(arr1[i])>1):
        arr1[i].sort()
for i in range(p):
    print("%06d%06d"%(arr[i][0],bisect.bisect_right(arr1[arr[i][0]],arr[i][1])))
    #print("%06d%06d"%(arr[i][0],arr1[arr[i][0]].index(arr[i][1])+1))
### BUGGY CODE ###

from collections import Counter

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

S = Counter(listA)

##key##
key = S.keys()

##dict##
#my_dict = {}  

list_low = {}
list_high = {}

for i in key:
  num_low = (S[i]-1) * (S[i]-2) /2
  num_high =S[i] * (S[i]-1) /2
  list_low[i] = num_low
  list_high[i] = num_high

for i in listA:
  out =0
  for a in key:
    if i ==a:
      out = out + list_low[a]
    else:
      out = out + list_high[a]
  print(int(out))    


### FIXED CODE ###

from collections import Counter

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

S = Counter(listA)

##key##
key = S.keys()
out = 0
for i in key:
  out = out + S[i] * (S[i]-1) /2

for i in listA:
  test = out - S[i] * (S[i]-1) /2 + (S[i] -1) * (S[i]-2) /2
  print(int(test))
### BUGGY CODE ###

N, K = map(int, input().split(" "))
a = sorted(list(map(int, input().split(" "))))
nums = []
for i in range(N):
    for j in range(i + 1, N):
        nums.append(a[i] * a[j])
    if i + 2 <= N -1:
        if a[i + 1] * a[i + 2] > max(nums) and len(nums) >= K:
            print(sorted(nums)[K -1])
            exit()
print(sorted(nums)[K - 1])

### FIXED CODE ###

import bisect
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))

# 負の個数
num_neg = bisect.bisect_left(A, 0)
# 0の個数
num_zero = bisect.bisect_right(A, 0) - num_neg
# 正の個数
num_pos = N - num_neg - num_zero

A_neg_rev = A[:num_neg] # 絶対値が大きいものからになるようにソート
A_pos = A[num_neg + num_zero:] # 絶対値が小さいものからになるようにソート

A_neg = A_neg_rev[::-1] # 絶対値が大きいものからになるようにソート
A_pos_rev = A_pos[::-1] # 絶対値が小さいものからになるようにソート

# 値が0になるペアの個数
cnt_zero = num_zero * (num_pos + num_neg) + (num_zero * (num_zero - 1) // 2)
# 値が負になるペアの個数
cnt_neg = num_pos * num_neg

# 値が正になるとき
def syakutori_pos(arr, mid):
    if len(arr) == 0:
        return 0
    cnt = 0
    l = 0
    r = len(arr) - 1
    while l < r:
        if arr[l] * arr[r] <= mid:
            cnt += r - l
            l += 1
        else:
            r -= 1
    return cnt

# 値が負になるとき
def syakutori_neg(arr_pos, arr_neg, mid):
    if len(arr_pos) == 0 or len(arr_neg) == 0:
        return 0
    arr = arr_neg + arr_pos
    cnt = 0
    l = 0
    r = len(arr) - 1
    while l < len(arr_neg) and r >= len(arr_neg):
        if arr[l] * arr[r] <= mid:
            cnt += r - len(arr_neg) + 1
            l += 1
        else:
            r -= 1
    return cnt

# 自分以下の数になるペアの個数がK個以上になる
ok = 10 ** 18
ng = -ok - 1
while ng + 1 < ok:
    mid = (ok + ng) // 2
    cnt = 0
    if mid > 0:
        cnt += cnt_zero
        cnt += cnt_neg
        cnt += syakutori_pos(A_pos, mid) + syakutori_pos(A_neg, mid)
    elif mid == 0:
        cnt += cnt_zero
        cnt += cnt_neg
    else:
        cnt += syakutori_neg(A_pos_rev, A_neg_rev, mid)
    if cnt >= K:
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
strings = [[]*10 for i in range(n)]
for i in range(n):
    strings[i] = sorted(list(input()))

counter = 0
for i in range(n-1):
    for j in range(i+1,n):
        if strings[i] == strings[j]:
            counter +=1
print(counter)
        

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
strings = [[]*10 for i in range(n)]
for i in range(n):
    strings[i] = sorted(list(input()))

strings = sorted(strings)

succession = [0]*n
counter = 0
for i in range(1,n):
    if strings[i] == strings[i-1]:
        succession[i] = succession[i-1]+1
    if strings[i] != strings[i-1] and succession[i-1]>0:
        counter += (succession[i-1]+1)*succession[i-1]//2
    if i == n-1 and succession[i] >0:
        counter += (succession[i]+1)*succession[i]//2

print(counter)
### BUGGY CODE ###

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

for l in range(n-k+1):
  ans=max(ans,(k+sum(p[l:l+k]))/2)

print(ans)

### FIXED CODE ###

n,k=list(map(int,input().split()))
p=list(map(int,input().split()))
s=sum(p[0:k])
ans=(k+s)/2

for l in range(n-k):
  s-=p[l]
  s+=p[l+k]
  ans=max(ans,(k+s)/2)
print(ans)
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
sc = {i : k for i in range(1, n+1)}
sc[0] = 0

for s in a:
  for i in range(1, n+1):
    if i == s:
      continue
    
    sc[i] -= 1

del sc[0]
for s in sc.values():
  print("Yes" if s > 0 else "No")

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
sc = {i : 0 for i in range(1, n+1)}
sc[0] = 0

for s in a:
  sc[s] += 1

del sc[0]
for s in sc.values():
  print("Yes" if (k-q+s)>0 else "No")
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
cnt = 0
for i in range(n):
    if all(map(lambda pj: p[i] <= pj, p[:i + 1])):
        cnt += 1
        if p[i] == 1:
            break
print(cnt)

### FIXED CODE ###

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

cnt = 0
pjmin = P[0]
for pi in P:
    if pi <= pjmin:
        cnt +=1
        pjmin = pi
        if pi ==1:
            break
print(cnt)