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

import sys
sys.setrecursionlimit(10 ** 9)




def main():
    def ue(i, j):
        if lst_ue[i][j] != -1:
            return lst_ue[i][j]
        if lst[i][j] == '#':
            lst_ue[i][j] = 0
            return 0
        else:
            lst_ue[i][j] = ue(i-1, j) + 1
            return lst_ue[i][j]

    def shita(i, j):
        if lst_shita[i][j] != -1:
            return lst_shita[i][j]
        if lst[i][j] == '#':
            lst_shita[i][j] = 0
            return 0
        else:
            lst_shita[i][j] = shita(i+1, j) + 1
            return lst_shita[i][j]        

    def hidari(i, j):
        if lst_hidari[i][j] != -1:
            return lst_hidari[i][j]
        if lst[i][j] == '#':
            lst_hidari[i][j] = 0
            return 0
        else:
            lst_hidari[i][j] = hidari(i, j-1) + 1
            return lst_hidari[i][j]        

    def migi(i, j):
        if lst_migi[i][j] != -1:
            return lst_migi[i][j]
        if lst[i][j] == '#':
            lst_migi[i][j] = 0
            return 0
        else:
            lst_migi[i][j] = migi(i, j+1) + 1
            return lst_migi[i][j]        







    H, W = map(int, input().split())
    lst = [['#'] * (W+2)]
    lst += [['#'] + list(input()) + ['#'] for i in range(H)]
    lst += [['#'] * (W+2)]


    lst_ue = [[-1] * (W+2) for i in range(H+2)]
    lst_shita = [[-1] * (W+2) for i in range(H+2)]
    lst_migi = [[-1] * (W+2) for i in range(H+2)]
    lst_hidari = [[-1] * (W+2) for i in range(H+2)]
    
    ans = 0
    for i in range(1,H+1):
        for j in range(1, W+1):
            if lst[i][j] != '#':
                ans = max(ans, ue(i,j)+shita(i,j)+hidari(i,j)+migi(i,j)-3)
                if ans == H + W -1:
                    print (ans)
                    sys.exit()
    print (ans)
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

#上下方向の探索と左右方向の探索をまとめる
#まず表を完成させる-->全マスの探索
H, W = map(int, input().split())
lst = [['#'] * (W+2)]
lst += [['#'] + list(input()) + ['#'] for i in range(H)]
lst += [['#'] * (W+2)]


lst_ue = [[0] * (W+2) for i in range(H+2)]
lst_shita = [[0] * (W+2) for i in range(H+2)]
lst_migi = [[0] * (W+2) for i in range(H+2)]
lst_hidari = [[0] * (W+2) for i in range(H+2)]

for i in range(1, H+1):
    for j in range(1, W+1):
        lst_hidari[i][j] = 0 if lst[i][j] == '#' else 1 + lst_hidari[i][j-1]
    for j in range(W, 0, -1):
        lst_migi[i][j] = 0 if lst[i][j] == '#' else 1 + lst_migi[i][j+1]

for j in range(1, W+1):
    for i in range(1, H+1):
        lst_ue[i][j] = 0 if lst[i][j] == '#' else 1 + lst_ue[i-1][j]
    for i in range(H+1, 0, -1):
        lst_shita[i][j] = 0 if lst[i][j] == '#' else 1 + lst_shita[i+1][j]

ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        ans = max(ans, lst_ue[i][j]+lst_shita[i][j]+lst_migi[i][j]+lst_hidari[i][j]-3)

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

# -*- coding: utf-8 -*-
import sys
import numpy as np
input = sys.stdin.readline


def main():
    n = int(input())
    l = list(map(int, input().split()))
    index = np.argsort(l)

    result = 0
    for i in range(n-2):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                a = l[index[i]]
                b = l[index[j]]
                c = l[index[k]]
                if b < a + c and c < a + b:
                    result += 1

    print(result)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()

    result = 0
    for i in range(n-2):
        for j in range(i + 1, n - 1):
            result += bisect.bisect_left(l, l[i] + l[j]) - (j + 1)

    print(result)


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

N = int(input())
S = [''.join(sorted(input())) for _ in range(N)]
'''
d = {}
for s in S:
  if s not in d:
    d[s] = 0
  d[s] += 1
  
ans = 0
for k, v in d.items():
  for i in range(v):
    for j in range(i+1,v):
      ans += 1
'''
ans = 0
for i in range(len(S)):
  s1 = S[i]
  for j in range(i+1,len(S)):
    s2 = S[j]
    if s1 == s2:
      ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = [''.join(sorted(input())) for _ in range(N)]

def helper(s):
  d = {}
  for c in s:
    if c not in d:
      d[c] = 0
    d[c] += 1
  
  return d

def pairs(n):
    return int(n * (n - 1) / 2)

d = {}
for s in S:
  if s not in d:
    d[s] = 0
  d[s] += 1

ans = sum([pairs(v) for v in d.values() if v > 1])
  
print(ans)
### BUGGY CODE ###

N = int(input())
s=[]
for i in range(N):
  flag = 0
  a = input()
  for i in range(len(s)):
    if(s[i] == a):
      flag += 1
  if(flag == 0):
    s.append(a)
print(len(s))

### FIXED CODE ###

import collections
N = int(input())
s=[]
for i in range(N):
  s.append(input())
c = collections.Counter(s)
 
print(len(c))
### BUGGY CODE ###

s=input()
ls=len(s)
now=[1]*ls
chlist=[]
while(1):
  tmp=[0]*ls
  for i in range(ls):
    if s[i]=="R":
      tmp[i+1]+=now[i]
    else:
      tmp[i-1]+=now[i]
  now=tmp
  if now in chlist:
    st=chlist.index(now)
    break
  else:
    chlist.append(now)
ch=chlist[st:]
idx=(10*100-st)%len(ch)-1
ans=[str(i) for i in ch[idx]]
print(" ".join(ans))

### FIXED CODE ###

s=input()
ls=len(s)
ans=[0]*ls
s+="R"
rst=lst=lend=0
for i in range(1,ls):
  if s[i]=="L" and lst==0:
    lst=i
  if lst==0:
    continue
  if s[i+1]=="R":
    lend=i
  if lend==0:
    continue
  ans[lst-1]=(lst-1-rst)//2+1+(lend-lst+1)//2
  ans[lst]=(lst-1-rst+1)//2+(lend-lst)//2+1
  rst=lend+1
  lst=lend=0

an=[str(i) for i in ans]
print(" ".join(an))
### BUGGY CODE ###

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

old_score = 1
new_score = 1

for i in range(n - k + 1): #iはスタート地点
    old_score = new_score
    new_score = 1
    for j in range(i, i + k): #Aのj番目の要素をかける
        new_score = new_score * A[j]

    if i != 0 and old_score < new_score:
        print("Yes")
    elif i != 0 and old_score >= new_score:    
        print("No")

### FIXED CODE ###

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

for i in range(n - k): #iはスタート地点
    old = A[i] #Aのj番目の要素をかける
    new = A[i + k]
    
    if old < new:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N = int(input())
P = [int(p) for p in input().split()]
ans = 0

for i in range(N):
  if P[i] == min(P[0:i+1]) :
    ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
P = [int(p) for p in input().split()]
ans = 0
mi = P[0]
for i in range(N):
  mi = min(mi, P[i])
  if mi >= P[i]:
    ans += 1 
print(ans)
### BUGGY CODE ###

from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def main():
  n, m = LI()

  if m%2==1:
    print(-1)
    exit()

  graph = defaultdict(set)
  grapht = defaultdict(set)
  for i in range(m):
    a, b = LI()
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)
    grapht[a].add(b)
    grapht[b].add(a)

  graph2 = defaultdict(set)
  visited = [0 for i in range(n)]
  num = [1 for i in range(n)]

  def dfs(x):
    visited[x] = 1

    for nx in graph[x]:
      if not visited[nx]:
        dfs(nx)

    t = set()
    if num[x]==1 and len(grapht[x])%2==0:
      for e in grapht[x]:
        graph2[x].add(e)
        t.add(e)
    elif num[x]==-1 and len(grapht[x])%2==0:
      for j, e in enumerate(grapht[x]):
        if j==len(grapht[x])-1:
          graph2[e].add(x)
          num[e] *= -1
        else:
          graph2[x].add(e)
        t.add(e)
    elif num[x]==1 and len(grapht[x])%2==1:
      for j, e in enumerate(grapht[x]):
        if j==len(grapht[x])-1:
          graph2[e].add(x)
          num[e] *= -1
        else:
          graph2[x].add(e)
        t.add(e)
    elif num[x]==-1 and len(grapht[x])%2==1:
      for e in grapht[x]:
        graph2[x].add(e)
        t.add(e)
    for e in t:
      grapht[x].remove(e)
      grapht[e].remove(x)

  dfs(0)

  for i in range(n):
    for e in graph2[i]:
      print(i+1, e+1)

if __name__ == '__main__':
  main()

### FIXED CODE ###

from collections import defaultdict
import sys

def dfs(visited, graph, grapht, graph2, num, x):
  visited[x] = 1

  for nx in graph[x]:
    if not visited[nx]:
      dfs(visited, graph, grapht, graph2, num, nx)

  t = set()
  if num[x]==1 and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  elif num[x]==-1 and len(grapht[x]) and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  elif num[x]==1 and len(grapht[x])%2==1:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  else:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  for e in t:
    if e in grapht[x]:
      grapht[x].remove(e)
    if x in grapht[e]:
      grapht[e].remove(x)

if __name__ == "__main__":
  sys.setrecursionlimit(1000000)
  input = sys.stdin.readline
  n, m = map(int, input().split())

  if m%2==1:
    print(-1)
    exit()

  graph = defaultdict(set)
  grapht = defaultdict(set)
  for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)
    grapht[a].add(b)
    grapht[b].add(a)

  graph2 = defaultdict(set)
  visited = [0]*n
  num = [1]*n

  dfs(visited, graph, grapht, graph2, num, 0)

  for i in range(n):
    if len(graph2[i])%2==1:
      print(-1)
      exit()

  for i in range(n):
    for e in graph2[i]:
      print(i+1, e+1)
### BUGGY CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(input())
p = []
ans = 0
for i in range(n):
    if s[i] in p:
        pass
    else:
        p.append(s[i])
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
s = []
p = set()
ans = 0
for i in range(n):
    s.append(input())
    if s[i] in p:
        pass
    else:
        p.add(s[i])
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
x,y = map(int,input().split())
mod = 10**9+7
def count_route(x,y):
  if x<=0 or y<=0:
    return 0
  elif x/y>2 or y/x>2:
    return 0
  elif x%y==0 and x//y==2:
    return 1
  elif y%x==0 and y//x==2:
    return 1
  else:
    return sum([count_route(x-1,y-2)%mod,count_route(x-2,y-1)%mod])
print(count_route(x,y))


### FIXED CODE ###

x,y = map(int,input().split())
mod = 10**9+7
def comb(a,b):
  comb = 1
  chld = 1
  for i in range(b):
    comb = comb*(a-i)%mod
    chld = chld*(b-i)%mod
  return (comb*pow(chld,mod-2,mod))%mod
if (x+y)%3!=0:
  print(0)
else:
  nm = (x+y)//3
  n = y-nm
  m = x-nm
  if n>=0 and m>=0:
    print(comb(n+m,m))
  else:
    print(0)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(x) for x in input().split()]
for i in range(m):
  b,c = map(int,input().split())
  cnt = 0
  a = sorted(a)
  for j in range(n):
    if a[j] < c:
      a[j] = c
      cnt += 1
    if cnt == b:
      break
print(sum(a))

### FIXED CODE ###

# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop, heapify
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


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

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    n, m = LI()
    a = sorted(list(LI()))
    # 1. c以下をcに毎回置き換え.
    # for i in range(m):
    #     b, c = LI()
    #     for j in range(b):
    #         if a[j] > c:
    #             break
    #         heappushpop(a, c)
    # print(sum(a))

    # 2. 大きいcから入れていってbの累計がlen(a)になったら即終わり.
    # bc = LIR(m)
    # bc.sort(key=lambda x: x[1])
    # cnt = 0
    # for pair in bc:
    #     heappushpop(a, pair[1])
    #     cnt += pair[0]
    #     if cnt > len(a):
    #         break
    # print(sum(a))

    bc = LIR(m)
    bc.sort(key=lambda x: x[1], reverse=True)
    d = []
    i = 0
    while len(d) < n and i < len(bc):
        if bc[i][0] + len(d) < n:
            d.extend([bc[i][1]] * bc[i][0])
        else:
            d.extend([bc[i][1]] * (n - len(d)))
            break
        i += 1
    for i in range(len(d)):
        if d[i] < a[i]:
            break
        a[i] = d[i]
    print(sum(a))


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

import math
from functools import reduce

def gcd(*numbers):
  return reduce(math.gcd, numbers)

K = int(input())
sum = 0
for a in range(1, K + 1):
  for b in range(1, K + 1):
    for c in range(1, K + 1):
      sum += gcd(a, b, c)
print(sum)

### FIXED CODE ###

def gcd(p, q):
  while q != 0:
    r = p % q
    p = q
    q = r
  return p

K = int(input())
sum = 0
for a in range(1, K + 1):
  for b in range(1, K + 1):
    for c in range(1, K + 1):
      sum += gcd(gcd(a, b), c)
print(sum)
### BUGGY CODE ###

N, M, Q = map(int, input().split(" "))
route = []
question = []
for i in range(M):
    route.append(list(map(int, input().split(" "))))
for i in range(Q):
    question.append(list(map(int, input().split(" "))))

route = sorted(route, key=lambda x: x[1])
# question = sorted(question, key=lambda x: x[1])

ans = [0 for i in range(Q)]
chk = 0
for j in range(Q):
    for i in range(M):
        if route[i][1] > question[j][1]:
            break
        if (question[j][0] <= route[i][0]) and (route[i][1] <= question[j][1]):
            ans[j] += 1

for a in ans:
    print(a)

### FIXED CODE ###

# coding: utf-8
# Your code here!

N, M, Q = map(int, input().split(" "))
L = []
R = []
p = []
q = []

for i in range(M):
    _L, _R = map(int, input().split(" "))
    L.append(_L)
    R.append(_R)
    
for i in range(Q):
    _p, _q = map(int, input().split(" "))
    p.append(_p)
    q.append(_q)
    
def buildSumTable(N, L, R):
    ret = [[0 for i in range(N+1)] for i in range(N+1)]
    for i in range(M):
        ret[L[i]][R[i]] += 1
    for i in range(1, N+1):
        for j in range(1, N+1):
            ret[i][j] += ret[i-1][j]
            ret[i][j] += ret[i][j-1]
            ret[i][j] -= ret[i-1][j-1]
    return ret

def getSumRange(table, p, q):
    return table[q][q] - table[q][p-1] - table[p-1][q] + table[p-1][p-1] 

sumTable = buildSumTable(N, L, R)

for i in range(Q):
    ans = getSumRange(sumTable, p[i], q[i])
    print(ans)
### BUGGY CODE ###

from collections import defaultdict
from sys import stdin
input = stdin.readline


def main():
  S = input()[:-1]
  MOD = 2019

  dp = [0]*(len(S)+1)
  dp[0] = 0

  ten = 1
  for i in range(1, len(S)+1):
    dp[i] = (dp[i-1] + ten*int(S[-i])) % MOD
    ten *= 10

  dic = defaultdict(int)
  sum_ = 0
  for sup in dp:
    if sup in dic:
      sum_ += dic[sup]
    dic[sup] += 1

  print(sum_)


if(__name__ == '__main__'):
  main()


### FIXED CODE ###

def main():
  # S = input()[-1:0:-1]
  S = input()[::-1]
  MOD = 2019

  # dp = [0]*(len(S)+1)
  # dp[0] = 0
  dic = [0]*2019
  dic[0] = 1

  ten = 1
  pre = 0
  for i, s in enumerate(S):
    # dp[i] = (dp[i-1] + ten*int(s)) % MOD
    pre = (pre + ten*int(s)) % MOD
    dic[pre] += 1
    ten *= 10
    ten %= MOD

  sum_ = 0
  # for sup in dp:
  #   dic[sup] += 1

  for v in dic:
    sum_ += v*(v-1)//2

  print(sum_)


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

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

ans =1
now = [1]
ed = set([1])

for i in range(k):
    if a[now[i]-1] in ed:
        break
    now.append(a[now[i]-1])
    ed = set(now)
    
t = len(now)-now.index(a[now[i]-1])
f = now.index(a[now[i]-1])


if k >= f + t:
    p = (k-f)%t
    k = f + p
    

print(now[k])

### FIXED CODE ###

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

visited = [None]*n
cur = 0
for i in range(k):
    if visited[cur] is None:
        visited[cur] = i
        cur = a[cur]-1
    else:
        break
else:
    print(cur+1)
    sys.exit()

k -= i
k %= i-visited[cur]

for i in range(k):
    cur = a[cur]-1

print(cur+1)
### BUGGY CODE ###

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

# for i in range(1,N):
#     # print(P[i],P[i+1])
#     if P[i-1] <= P[i]:
#         print(i+1)
#         exit()

# print(N)

ans = 0

# 各部分列の最小値
minval = max(P)
for i in range(N):
    # arr = P[0],...,P[i]の最小値
    minval = min(minval,P[i])
    arr = P[0:i+1]

    # P[i]が最小値以下なら
    if P[i] <= minval:
        ans += 1
    
print(ans)


### FIXED CODE ###

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

ans = 0

# 各部分列の最小値
minval = max(P)
# for i in range(N):
for x in P:
    # arr = P[0],...,P[i]の最小値
    minval = min(minval,x)

    # P[i]が最小値以下なら
    if x <= minval:
        ans += 1
    
print(ans)
### BUGGY CODE ###

N = int(input())

A = []

def search(n):
    len_a = len(A)
    if len_a == 0:
        A.append(n)
        return 1
    left = 0
    right = len_a-1
    while left < right:
        mid = (left+right) // 2
        if A[mid] == n:
            break
        elif n < A[mid]:
            right = mid-1
        else:
            left = mid+1

    mid = (left + right) // 2
    if A[mid] >= n:
        while mid >= 0:
            if A[mid] < n:
                A[mid] = n
                return 0
            mid -= 1
        if mid == -1:
            A.insert(0, n)
            return 1
    elif A[mid] < n:
        A[mid] = n
        return 0

ans = 0
for _ in range(N):
    a = int(input())
    ans += search(a)

print(ans)

### FIXED CODE ###

from collections import deque
import bisect
N = int(input())
A = deque()
for _ in range(N):
    x = int(input())
    i = bisect.bisect_left(A,x)
    if i == 0:
        A.appendleft(x)
    else:
        A[i-1] = x

print(len(A))
### BUGGY CODE ###

MOD = 998244353

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

S = sum(A)
memo0 = [0] * (S+1)
memo1 = [0] * (S+1)
memo0[0] = 1
memo1[0] = 1


# なんで大きい方から小さくしていくのか
def dp0():
    for i in range(n):
        for s in range(S, A[i]-1, -1):
            memo0[s] = (memo0[s] + memo0[s-A[i]]*2) % MOD


# 辺を2グループにわけるDP
def dp1():
    for i in range(n):
        for s in range(S, A[i]-1, -1):
            memo1[s] = (memo1[s] + memo1[s-A[i]]) % MOD


dp0()
dp1()
# 実装方法を変える
ans = pow(3, n, MOD)
# 解から三角形が存在しない通りを引く
for l in range(0, S//2+1):
    ans = (ans - memo0[l]*3) % MOD
# 引きすぎた分を引く
if S % 2 == 0:
    ans = (ans + memo1[S//2]*3) % MOD


print(ans)


### FIXED CODE ###

MOD = 998244353

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

S = sum(A)
memo0 = [0] * (S+1)
memo1 = [0] * (S+1)
memo0[0] = 1
memo1[0] = 1


# なんで大きい方から小さくしていくのか
def dp0():
    for i in range(n):
        for s in range(S, A[i]-1, -1):
            memo0[s] = (memo0[s] + memo0[s-A[i]]*2) % MOD


# 辺を2グループにわけるDP
def dp1():
    for i in range(n):
        for s in range(S, A[i]-1, -1):
            memo1[s] = (memo1[s] + memo1[s-A[i]]) % MOD


dp0()
dp1()
# 実装方法を変える
ans = pow(3, n, MOD)
# 解から三角形が存在しない通りを引く
for l in range(0, S//2+1):
    ans = (ans - memo0[l]*3) % MOD
# 引きすぎた分を引く
if S % 2 == 0:
    ans = (ans + memo1[S//2]*3) % MOD


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

from collections import Counter
# si と sj のアナグラムは Counter(si)==Counter(sj) で求められる
# 組の数を数える
N=int(input())
S=[Counter(input()) for n in range(N)]
c=0
l=[]
for s in S:
    if s in l:
        continue
    else:
        l.append(s)
        c+=(S.count(s)*(S.count(s)-1))//2
print(c)



### FIXED CODE ###

N=int(input())
S=["".join(sorted(input())) for n in range(N)]
d={}
for s in S:
    if s not in d:
        d[s]=1
    else:
        d[s]+=1
c=0
for k in d:
    n=d[k]
    c+=(n*(n-1))//2
print(c)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().strip().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q

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

def func(A,b,c):
    for i in range(len(A)):
        if A[i]==b:
            A[i]=c

for i in range(Q):
    func(A,B[i],C[i])
    print(sum(A))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().strip().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q
from collections import Counter
K=Counter(A)
ans = 0

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


for i in K:
    ans += i * K[i]

for i in range(Q):
    ans -= B[i] * K[B[i]]
    ans += C[i] * K[B[i]]
    K[C[i]] += K[B[i]]
    K[B[i]] = 0
    print(ans)
### BUGGY CODE ###

# n, m, l = map(int, input().split())

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import sys
input = sys.stdin.readline

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

if 1 not in A:
    print(-1)
    exit()

tempA = A.copy()
i = 1
while i in tempA:
    k = tempA.index(i) + 1
    tempA = tempA[k:]
    i += 1

print(N-(i-1))


### FIXED CODE ###

# n, m, l = map(int, input().split())

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import sys
input = sys.stdin.readline

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

n = 1
ans = 0
for i in A:
    if i == n:
        n += 1
    else:
        ans += 1
if n == 1:
    print(-1)
else:
    print(ans)