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

def has_duplicates(seq):
    return len(seq) == len(set(seq))
def main():
    n=int(input())
    l=list(map(int,input().split()))
    tel=[-1,-1,-1]
    temp=0
    bn=0
    tc=0
    pc=0
    i=0
    while len(bin(i))-3<n:
        bn=bin(i)
        if str(bn).count('1')==3:
            tc=0
            tel=[-1,-1,-1]
            for j in range(len(str(bn)[2:])):
                if (i>>j)&1:
                    tel[tc]=l[n-j-1]
                    tc+=1
            if has_duplicates(tel):
                tel.sort()
                if abs(tel[1]-tel[2])<tel[0] and tel[0] < tel[1]+tel[2]:
                    pc+=1
        i+=1
    print(pc)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n=int(input())
    l=list(map(int,input().split()))
    ans=0
    for i in range(n):
        for k in range(i+1,n):
            for j in range(k+1,n):
                temp=[l[i],l[k],l[j]]
                if len(set(temp))==len(temp):
                    temp.sort()
                    if temp[0]+temp[1]>temp[2]:
                        ans+=1
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,K = map(int, input().split())
P = list(map(int, input().split()))
P_max = 0
for i in range(len(P)):
    P_new = P[i:i+K]
    P_sum = sum(P_new)
    if P_sum > P_max:
        P_max = P_sum
print(P_max/2+0.5*K)

### FIXED CODE ###

N,K = map(int, input().split())
P = list(map(int, input().split()))
P_sum = 0
for i in range(K):
    P_sum += P[i]
P_max = P_sum
for i in range(N-K):
    P_sum = P_sum + P[K+i]-P[i]
    if P_sum > P_max:
        P_max = P_sum
print(P_max/2+0.5*K)
### BUGGY CODE ###

N, M = map(int, input().split())
ans = 1
for i in range(2,int(M/N)+1):
	if M%i == 0:
		ans = i
	else:
		pass
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
d = []
for i in range(1, int(M**0.5)+1):
	if M%i == 0:
		d.append(i)
		d.append(M//i)
d.sort()
for i in range(1,len(d)+1):
	if d[-i] <= M//N:
		print(d[-i])
		exit()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from sys import stdin

import time
import numpy as np
import math



############################################

# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])
temp = stdin.readline().split()
data = temp[0]


out = 0

if N > 2:
    for ii, i in enumerate(data[:-2]):
        for jj,j in enumerate(data[ii+1:-1]):
            jj = jj+ii+1
            if i!=j:
                sum1 = 0                    
                for d in np.asarray([d for d in "RGB"]):
                    if i!=d and j!=d:
                        sum1 = np.sum(np.asarray([d for d in data[jj+1:]])==d)
                        let = d
                out+=sum1
                if jj+jj-ii<N:
                    if data[jj+jj-ii]==let:                    
                        out-=1
print(out)



### FIXED CODE ###

# -*- coding: utf-8 -*-

############################################

# read data for n sequences.
N = int(input())
data = input()

out = 0
r=0;g=0;b=0;
for d in data:
    if d =="R":
        r+=1
    elif d=="B":
        b+=1
    else:
        g+=1
out = r*g*b

if N > 2:
    for ii, i in enumerate(data[:-2]):
        for jj,j in enumerate(data[ii+1:-1]):
            jj = jj+ii+1
            if i!=j:
                sum1 = 0                    
                for d in [d for d in "RGB"]:
                    if i!=d and j!=d:
                        let = d

                if jj+jj-ii<N:
                    if data[jj+jj-ii]==let:                    
                        out-=1
print(out)
### BUGGY CODE ###

A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
tickets = {}
for _ in range(M):
    x, y, c = map(int, input().split())
    if (x, y) in tickets:
        if tickets[(x, y)] < c:
            tickets[(x, y)] = c
    else:
        tickets[(x, y)] = c

min_price = float("inf")
for i, price_a in enumerate(a, 1):
    for j, price_b in enumerate(b, 1):
        total_price = price_a + price_b
        if (i, j) in tickets:
            total_price -= tickets[(i, j)]
        if min_price > total_price:
            min_price = total_price

print(min_price)

### FIXED CODE ###

A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

min_price = min(a) + min(b)
for _ in range(M):
    x, y, c = map(int, input().split())
    discount_price = a[x-1] + b[y-1] - c
    if min_price > discount_price:
        min_price = discount_price
        
print(min_price)
### BUGGY CODE ###

from sys import stdin
#import numpy as np

readline = stdin.readline

N, Q = map(int, readline().split())
C = list(map(int, readline().split()))
S = [list(map(int, readline().split())) for _ in range(Q)]

def main(N, Q, C, S):    
  # Binary Indexed Tree 
  # https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
  b = [0 for _ in range(N+1)]
  def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
      res_sum += b[idx]
      idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum
  def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
      b[idx] += x
      idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

  loc = [0 for _ in range(N)] #各種類の玉のうちの最右端の所在地
  S = [[S[i][1], S[i][0], i] for i in range(Q)] #クエリ
  S.sort() #区間の右端でソート
  #S = np.array(S, dtype = np.int64)
  #print(S)
  ans = [0 for _ in range(Q)]
  k = 0
  for j in range(N):
    if loc[C[j]-1] > 0: #玉の更新
      BIT_update(loc[C[j]-1], -1)
    loc[C[j]-1] = j+1
    BIT_update(j+1, 1)  
    
    if S[k][0] == j+1:
      t = BIT_query(j+1)
    while k < len(S) and S[k][0] == j+1: #クエリへの返答
      ans[S[k][2]] = t - BIT_query(S[k][1]-1)
      k += 1
    if k == len(S):
      break
  return ans

ans = main(N, Q, C, S)
print(*ans, sep='\n')

### FIXED CODE ###

from sys import stdin
#import numpy as np

readline = stdin.readline

N, Q = map(int, readline().split()) 
C = list(map(int, readline().split())) 
S = [list(map(int, readline().split())) for _ in range(Q)] 
#print(S)
def main(N, Q, C, S):    
  # Binary Indexed Tree 
  # https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
  b = [0 for _ in range(N+1)]
  def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
      res_sum += b[idx]
      idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum
  def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
      b[idx] += x
      idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

  loc = [0 for _ in range(N)] #各種類の玉のうちの最右端の所在地
  S = [(S[i], i) for i in range(Q)] #クエリ
  S.sort(key = lambda s: s[0][1]) #区間の右端でソート
  #S = np.array(S, dtype = np.int64)
  #print(S)
  ans = [0 for _ in range(Q)]
  k = 0
  for j in range(N):
    if loc[C[j]-1] > 0: #玉の更新
      BIT_update(loc[C[j]-1], -1)
    loc[C[j]-1] = j+1
    BIT_update(j+1, 1)  
    
    if S[k][0][1] == j+1:
      t = BIT_query(j+1)
    while k < len(S) and S[k][0][1] == j+1: #クエリへの返答
      ans[S[k][1]] = t - BIT_query(S[k][0][0]-1)
      k += 1
    if k == len(S):
      break
  return ans

ans = main(N, Q, C, S)
print(*ans, sep='\n')
### BUGGY CODE ###

l,r = map(int,input().split())
ans = 2019
for i in range(l,r):
    for j in range(i+1,r+1):
        a = (i*j)%2019
        ans = min(ans,a)
        if a == 0:
            break
        else:
            continue
        break
print(ans)

### FIXED CODE ###

l,r = map(int,input().split())
value = 2019
if r - l > 2019:
    print(0)
else:
    l1 = l%2019
    r1 = r%2019
    ans = 100000000
    if r1>l1:
        for i in range(l,r):
            for j in range(i+1,r+1):
                if ans>(i*j)%2019:
                    ans = (i*j)%2019
        print(ans)
    else:
        print(0)
### BUGGY CODE ###

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

for i in range(N-1):
    minh = min(H[i+1:]) # i+1以降のリストをスライス
    if H[i] - minh >= 2:
        print('No')
        break
    else:
        continue
else:
    print('Yes')

"""
# よく考えたら最大だけじゃダメだった
m = H.index(max(H)) # 複数の候補がある場合は最初のインデックスを返す
print(m)
for i in range(m+1, N):
    if H[m] - H[i] >= 2:
        print('No')
        break
    else:
        continue
else:
    print('Yes')
"""

### FIXED CODE ###

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

highest = 0
for i in range(N-1):
    highest = max(highest, H[i])
    if highest - 1 <= H[i+1]:
        continue
    else:
        print('No')
        break
else:
    print('Yes')
### BUGGY CODE ###

x, y, z, k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort(reverse=1)
B.sort(reverse=1)
C.sort(reverse=1)

D = [0] * (min(k, x) * min(k, y))

for i in range(min(k, x)):
    for j in range(min(k, y)):
        D.append(A[i] + B[j])

D.sort(reverse=1)
E = [0] * (min(k, len(D)) * min(k, z))

for i in range(min(k, len(D))):
    for j in range(min(k, z)):
        E.append(D[i] + C[j])

E.sort(reverse=1)

for i in range(k):
    print(E[i])

### FIXED CODE ###

x, y, z, k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort(reverse=1)
B.sort(reverse=1)
C.sort(reverse=1)

D = [0] * (min(k, x) * min(k, y))

for i in range(min(k, x)):
    for j in range(min(k, y)):
        D.append(A[i] + B[j])

D.sort(reverse=1)
E = [0] * (min(k, len(D)) * min(k, z))

for i in range(min(k, len(D))):
    for j in range(min(k, z)):
        E.append(D[i] + C[j])

E.sort(reverse=1)

for i in range(k):
    print(E[i])
### BUGGY CODE ###

import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()

fact = [1]*(n+1)
for i in range(2,n+1):
    fact[i] = fact[i-1]*i

def cmb(n, r):
    return fact[n]//(fact[r]*fact[n-r])

a.sort(reverse = True)
res = 0
for i in range(n-k+1):
    res += a[i] * fact[n-i-1]//(fact[k-1]*fact[n-i-k])

a.reverse()
for i in range(n-k+1):
    res -= a[i] * fact[n-i-1]//(fact[k-1]*fact[n-i-k])

print(res%MOD)

### FIXED CODE ###

import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()

def mpow(a, n):
    if n == 0:return 1
    if n == 1:return a%MOD
    if n%2 == 1:return (a%MOD * mpow(a, n-1)%MOD)%MOD
    t = mpow(a, n//2)
    return (t*t)%MOD

fac = [1]*(n+1)
inv_fac = [1]*(n+1)
for i in range(n):
    fac[i+1] = (fac[i]*(i+1))%MOD
inv_fac[n] = mpow(fac[n], MOD-2)
for i in range(n, 0, -1):
    inv_fac[i-1] = (inv_fac[i]*i)%MOD

def cmb(n, r):
    if n == 0 and r == 0:return 1
    if n<r or n<0:return 0
    return (fac[n]*(inv_fac[r]*inv_fac[n-r])%MOD)%MOD
 
a.sort(reverse = True)
res = 0
for i in range(n-k+1):
    res += (a[i]*cmb(n-i-1, k-1))%MOD
    res = res%MOD
 
a.reverse()
for i in range(n-k+1):
    res -= (a[i]*cmb(n-i-1, k-1))%MOD
    res = res%MOD
 
print(res)
### BUGGY CODE ###

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

M = [(1+p)/2 for p in P]
result = 0

for i in range(N-K+1):
    tmp = sum(M[i:i+K])
    if result<tmp:
        result=tmp

print(result)

### FIXED CODE ###

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

M = [(1+p)/2 for p in P]
result = [0, ]

for i in range(1, N-K+1):
    result.append(result[-1] + M[i+K-1] - M[i-1])

print(sum(M[:K]) + max(result))
### BUGGY CODE ###

N = int(input())
S = input()

stoi = {'R':0, 'G':1, 'B':2}
itos = {1:'R', 2:'G', 3:'B'}
li = [[0] * 3 for _ in range(N)]
ans = 0

for ind, s in enumerate(S):
    if(ind == 0):
        li[ind][stoi[s]] = 1
    else:
        li[ind] = li[ind - 1].copy()
        li[ind][stoi[s]] += 1

for i in range(N):
    for j in range(i + 1, N):
        if(S[i] == S[j]):
            continue
        k = 2 * j - i
        kc = 6 - (stoi[S[i]] + stoi[S[j]] + 2)
        res = li[-1][kc-1] - li[j][kc-1]
        if(k<N):
            if(kc == stoi[S[k]] + 1):
                res -= 1
        ans += res

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

stoi = {'R':0, 'G':1, 'B':2}
itos = {1:'R', 2:'G', 3:'B'}
li = [[0] * N for _ in range(3)]
ans = 0

for ind, s in enumerate(S):
    if(ind == 0):
        li[stoi[s]][ind] = 1
    else:
        for i in range(3):
            li[i][ind] = li[i][ind - 1]
        li[stoi[s]][ind] += 1

for i in range(N):
    for j in range(i + 1, N):
        if(S[i] == S[j]):
            continue
        k = 2 * j - i
        kc = 6 - (stoi[S[i]] + stoi[S[j]] + 2)
        res = li[kc-1][-1] - li[kc-1][j]
        if(k < N and kc == stoi[S[k]] + 1):
            res -= 1
        ans += res

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

import itertools

def main():
    # 8通りの方法を調べて最大値　-,-,- から +,+,+
    N, M = map(int, input().split())

    data = [[0] * 8 for _ in range(M+1)]
    p = list(itertools.product([-1, 1], repeat=3))

    for i in range(N):
        #print(data)
        x, y, z = map(int, input().split())
        for k in range(M-1, -1, -1):
            for j in range(8):
                tmp = x * p[j][0] + y * p[j][1] + z * p[j][2]
                if data[k+1][j] < data[k][j] + tmp:
                    data[k+1][j] = data[k][j] + tmp
    answer = 0
    for d in data[M]:
        if abs(d) > answer:
            answer = abs(d)
    print(answer)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import itertools

def main():
    # 8通りの方法を調べて最大値　-,-,- から +,+,+
    N, M = map(int, input().split())

    data = [[] for i in range(8)]
    p = list(itertools.product([-1, 1], repeat=3))

    for i in range(N):
        #print(data)
        x, y, z = map(int, input().split())
        for j in range(8):
            tmp = x * p[j][0] + y * p[j][1] + z * p[j][2]
            data[j].append(tmp)
               
    answer = 0
    for d in data:
        d.sort(reverse=True)
        s = sum(d[:M])
        if abs(s) > answer:
            answer = abs(s)
    print(answer)

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

n = int(input())
s = [str(input()) for _ in range(n)]
abc_str = 'abcdefghijklmnopqrstuvwxyz'
anagram_lst = []
number = 0

def count_lst(x):
    count_lst = [0]*26
    for j in range(10):
        abc = x[j]
        for k in range(26):
            if abc==abc_str[k]:
                count_lst[k] += 1
                break
    return count_lst

def addition(n):
    answer = 0
    for i in range(1,n+1):
        answer += i
    return answer

for i in range(n):
    string = s[i]
    anagram_lst.append(count_lst(string))
    anagram_lst.sort()

count = 1
for i in range(n-1):
    anagram1 = anagram_lst[i]
    anagram2 = anagram_lst[i+1]
    if anagram1==anagram2:
        count +=1
        if i==n-2:
            number += addition(count-1)
    else:
        number += addition(count-1)
        count = 1

print(number)

### FIXED CODE ###

n = int(input())
s = [str(input()) for _ in range(n)]
abc_str = 'abcdefghijklmnopqrstuvwxyz'
anagram_lst = []
number = 0

def count_lst(x):
    count_lst = [0]*26
    for j in range(10):
        abc = x[j]
        for k in range(26):
            if abc==abc_str[k]:
                count_lst[k] += 1
                break
    return count_lst

def addition(n):
    answer = 0
    for i in range(1,n+1):
        answer += i
    return answer

for i in range(n):
    string = s[i]
    anagram_lst.append(count_lst(string))

anagram_lst.sort()
count = 1
for i in range(n-1):
    anagram1 = anagram_lst[i]
    anagram2 = anagram_lst[i+1]
    if anagram1==anagram2:
        count +=1
        if i==n-2:
            number += addition(count-1)
    else:
        number += addition(count-1)
        count = 1

print(number)
### BUGGY CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N = int(input())

prime_L = prime_factorize(N)
n = len(prime_L)
sum = 10 ** 13

for i in range(2 ** n):
    bit = str(format(i, 'b')).zfill(n)
    total_a = 1
    total_b = 1
    for j in range(n):
        if bit[j] == '0':
            total_a = total_a * prime_L[j]
        elif bit[j] == '1':
            total_b = total_b * prime_L[j]
    if total_a + total_b - 2 < sum:
        sum = total_a + total_b - 2
print(sum)


### FIXED CODE ###

import  math

N = int(input())

root = int(math.sqrt(N))
sum = 10 ** 13

for i in range(1, root + 2):
    if N % i == 0 and int(N / i) + i - 2 < sum:
        sum = int(N / i) + i - 2

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

N,K = map(int, input().strip().split(' '))
S = input().strip()

# 奇数番目は1のカタマリの人数　偶数番目は0のカタマリの人数 両端は必ず1のカタマリの人数
now_state, now_count = '1', 0
L = []
Ladd = L.append
for i in range(len(S)):
  if S[i] == now_state:
    now_count += 1
  else:
    Ladd(now_count)
    # reset
    now_count = 1
    now_state = '1' if now_state == '0' else '0'
Ladd(now_count)
if now_state == '0':
  Ladd(0)

j = min(int((len(L)-1)/2), K) # 0のカタマリをひっくり返せるだけひっくり返す
print(max([sum(L[i:i+j*2+1]) for i in range(len(L)-j*2) if i%2==0]))

### FIXED CODE ###

N,K = map(int, input().strip().split(' '))
S = input().strip()
l,r,now_max,now_zeros = 0,0,1,0
for r in range(1,N):
  if S[r-1] == '0':
    if S[r] == '0':
      continue
    else:
      now_zeros += 1
  else:
    if S[r] == '0':
      if now_zeros < K:
        continue
      else:
        now_max = max(r-l, now_max)
        now_zeros -= 1
        for _ in range(l,r):
          l += 1
          if S[l-1:l+1] == '01':
            break
    else:
      continue
now_max = max(r-l+1, now_max)
print(now_max)
### BUGGY CODE ###

n=int(input())
A=[]
for i in range(0,n):
    A.extend([int(input())])
for j in range(0,n):
    s=A[j]
    A.pop(j)
    print(max(A))
    A.insert(j,s)

### FIXED CODE ###

import copy
from sys import stdin
n=int(input())
A=[int(stdin.readline().rstrip()) for _ in range(n)]
z=max(A)
B=sorted(A)
o=B[n-2]
for j in range(0,n):
    if A[j]<z:
       print(z)
    else:
        if B[n-2]==B[n-1]:
           print(z)
        else:
           print(o)
### BUGGY CODE ###

from collections import deque

N = int(input())

def pToHW(p):
    p = int(p) - 1
    return divmod(p, N)

P = list(map(pToHW, input().split()))

isFilled = [[False] * N for _ in range(N)]

def calcDist():
    minDist = [[10**18] * N for _ in range(N)]
    que = deque([])
    for h in range(N):
        if isFilled[h][0]:
            que.append((h, 0, 1))
        else:
            que.appendleft((h, 0, 0))
        if isFilled[h][N - 1]:
            que.append((h, N - 1, 1))
        else:
            que.appendleft((h, N - 1, 0))
    for w in range(1, N - 1):
        if isFilled[0][w]:
            que.append((0, w, 1))
        else:
            que.appendleft((0, w, 0))
        if isFilled[N - 1][w]:
            que.append((N - 1, w, 1))
        else:
            que.appendleft((N - 1, w, 0))

    while que:
        h, w, dist = que.popleft()

        if minDist[h][w] <= dist:
            continue
        minDist[h][w] = dist

        for toH, toW in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if not (0 <= toH < N and 0 <= toW < N):
                continue

            if isFilled[toH][toW]:
                que.append((toH, toW, dist + 1))
            else:
                que.appendleft((toH, toW, dist))
    return minDist

ans = 0
for h, w in P[::-1]:
    ans += calcDist()[h][w]
    isFilled[h][w] = True
print(ans)


### FIXED CODE ###

import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('solve', 'i4(i4, i4[:])')
    def solve(N, P):
        minDist = np.ones((N, N), dtype=np.int32)
        isFilled = np.ones((N, N), dtype=np.int32)

        for h in range(N):
            for w in range(N):
                minDist[h][w] = min(h, N - h - 1, w, N - w - 1)

        ans = 0
        for p in P:
            h, w = divmod(p, N)
            ans += minDist[h][w]
            isFilled[h][w] = False

            st = [(h, w)]
            while st:
                h, w = st.pop()
                dist = minDist[h][w] + isFilled[h][w]

                if h + 1 < N and minDist[h + 1][w] > dist:
                    minDist[h + 1][w] = dist
                    st.append((h + 1, w))
                if h - 1 >= 0 and minDist[h - 1][w] > dist:
                    minDist[h - 1][w] = dist
                    st.append((h - 1, w))
                if w + 1 < N and minDist[h][w + 1] > dist:
                    minDist[h][w + 1] = dist
                    st.append((h, w + 1))
                if w - 1 < N and minDist[h][w - 1] > dist:
                    minDist[h][w - 1] = dist
                    st.append((h, w - 1))
        return ans

    cc.compile()
    exit(0)

from my_module import solve

N = int(input())
P = np.asarray(list(map(lambda a: int(a) - 1, input().split())), dtype=np.int32)

print(solve(N, P))
### BUGGY CODE ###

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

a.sort()
dp = [True] * (max(a) + 1)
ans = 0

for i,num in enumerate(a):
    if dp[num-1]:
        j= 2 * num
        while j <= max(a):
            dp[j-1] = False
            j += num
        if not i+1==len(a):
            if a[i]==a[i+1]:
                dp[num-1] = False

for k in a:
    if dp[k-1]:
        ans += 1

#print(dp)
print(ans)

### FIXED CODE ###

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

a.sort()
dp = [True] * a[-1]
ans = 0

for i,num in enumerate(a):
    if dp[num-1]:
        j= 2 * num
        while j <= a[-1]:
            dp[j-1] = False
            j += num
        if not i+1==len(a):
            if a[i]==a[i+1]:
                dp[num-1] = False

for k in a:
    if dp[k-1]:
        ans += 1

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

import heapq
n=int(input())
A=[int(i) for i in input().split()]
AL=A[:n]
AR=[]
for i in range(2*n,3*n):
  AR.append(-A[i])
ALS,ARS=[0]*(n+1),[0]*(n+1)
ALS[0],ARS[0]=sum(AL),-sum(AR)
heapq.heapify(AL)
heapq.heapify(AR)
for i in range(n):
  heapq.heappushpop(AL,A[n+i])
  ALS[i+1]+=sum(AL)
  heapq.heappushpop(AR,-A[2*n-i-1])
  ARS[i+1]+=-sum(AR)
ARS=ARS[::-1]
ans=-float("inf")
for i in range(n+1):
  ans=max(ans,ALS[i]-ARS[i])
print(ans)

### FIXED CODE ###

import heapq
n=int(input())
A=[int(i) for i in input().split()]
AL=A[:n]
AR=[0]*n
for i in range(2*n,3*n):
  AR[i-2*n]-=A[i]
ALS,ARS=[0]*(n+1),[0]*(n+1)
ALS[0],ARS[0]=sum(AL),sum(AR)
heapq.heapify(AL)
heapq.heapify(AR)
for i in range(n):
  l,r=A[n+i],-A[2*n-i-1]
  heapq.heappush(AL,l)
  ALS[i+1]=ALS[i]+l-heapq.heappop(AL)
  heapq.heappush(AR,r)
  ARS[i+1]=ARS[i]+r-heapq.heappop(AR)
ans=-float("inf")
for i in range(n+1):
  ans=max(ans,ALS[i]+ARS[n-i])
print(ans)
### BUGGY CODE ###

#インポート
import sys

#入力用
def ILI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def ISI(): return map(int, sys.stdin.readline().rstrip().split())
def II(): return int(sys.stdin.readline().rstrip())
def ISS(): return sys.stdin.readline().rstrip().split()
def IS(): return sys.stdin.readline().rstrip()

N = II()
sum = 0
for i in range(1, N+1):
    sum += i
print(sum-N)

### FIXED CODE ###

#インポート
import sys
 
#入力用
def ILI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def ISI(): return map(int, sys.stdin.readline().rstrip().split())
def II(): return int(sys.stdin.readline().rstrip())
def ISS(): return sys.stdin.readline().rstrip().split()
def IS(): return sys.stdin.readline().rstrip()
 
N = II()
sum = N*(1+N)//2
print(sum-N)