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

import sys
sys.setrecursionlimit(5000)

readline = sys.stdin.readline

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

# dp[i][j] = 左端がi、右端がjの状態でのX - Yの最高得点
# dp[0][-1] = 0
# 奇数回目の処理では、
# dp[i][j] = max(dp[i-1][j] + A[i],dp[i][j - 1] + A[j])
# 偶数回目の処理では、
# dp[i][j] = min(dp[i - 1][j]) + A[i],dp[i][j - 1] + A[j])

dp = [[-1] * (N + 1) for i in range(N + 1)]
def f(i,j):
  # 左端がi,右端がjのとき、これから取ることが出来る最大値 右端は含まない[i:j)
  if dp[i][j] != -1:
    return dp[i][j]
  if j - i == 1:
    if (N - (j - i)) % 2 == 0:
      return A[i]
    else:
      return -A[i]
  if (N - (j - i)) % 2 == 0:
    # 先手の場合
    dp[i][j] = max(f(i + 1,j) + A[i],f(i,j - 1) + A[j - 1])
    return dp[i][j]
  else:
    dp[i][j] = min(f(i + 1,j) - A[i],f(i,j - 1) - A[j - 1])
    return dp[i][j]
  
print(f(0,N))

### FIXED CODE ###

import sys
readline = sys.stdin.readline

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

# dp[i][j] = 元の数列の中の連続する区間i～jに対して、最終局面に行った時のX-Yの最大値

dp = [[0] * (N + 1) for i in range(N + 1)]
  
for length in range(1, N + 1):
  for i in range(N - length + 1):
    j = i + length
    
    if (N - length) % 2 == 0: # 先手番
      dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
      
    else: # 後手番
      dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])

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

from operator import mul
from functools import reduce
N = int(input())
a = list(map(int, input().split()))
c = reduce(mul, a)
if c > (10**18):
    print(-1)
else:
    print(reduce(mul, a))

### FIXED CODE ###

import sys

input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
if 0 in a:
    print(0)
    exit()
c = 1
l = 10 ** 18
for i in a:
    c *= i
    if c > l:
        print(-1)
        exit()

print(c)
### BUGGY CODE ###

from collections import deque
from numba import njit, b1, i4, i8, f8
import numpy as np
import sys

read = sys.stdin.read
readline = sys.stdin.readline

@njit((i8,i8,i8,i8,i8,i8,b1[:, :]), cache=True)
def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[0]*(W) for _ in range(H)]
  for i in range(H):
    for j in range(W):
      dist[i][j] = INF
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  que1 = [(C_h,C_w)]
  que2 = []
  i,j = 0,0

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]

  while True:
    if i==len(que1) and j==len(que2):
      break;
    while i<len(que1):
      h,w = que1[i]
      i += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
    while j<len(que2):
      h,w = que2[j]
      j += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = np.array([[c=='.' for c in readline()] for _ in range(H)])
solve(H,W,C_h,C_w,D_h,D_w,S)

### FIXED CODE ###

from collections import deque

H,W = map(int,input().split())
C_h,C_w = map(lambda x:int(x)-1,input().split())
D_h,D_w = map(lambda x:int(x)-1,input().split())
S = [input() for _ in range(H)]

INF = int(1e10)
dist = [[INF]*(W) for _ in range(H)]
deq = deque()
deq.append((C_h,C_w,0))

move_a = [(1,0),(0,1),(-1,0),(0,-1)]
move_b = [(i,j)for i in range(-2,2+1) for j in range(-2,2+1) if abs(i)+abs(j)>=2]

while len(deq):
  h,w,c = deq.popleft()
  if dist[h][w] <= c:
    continue
  dist[h][w] = c
  for dh,dw in move_a:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c:
      deq.appendleft((nh,nw,c))
  for dh,dw in move_b:
    nh,nw = h+dh,w+dw
    if nh<0 or nw<0 or nh>=H or nw>=W:
      continue
    if S[nh][nw] == '#':
      continue
    if dist[nh][nw] > c+1:
      deq.append((nh,nw,c+1))
  
print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)
### BUGGY CODE ###

MAX = 10 ** 6 + 5
N = int(input())
A = list(map(int, input().split()))
cnt = [0] * MAX
for a in A:
    cnt[a] += 1
for i in range(N):
    a = A[i]
    if cnt[a] == 0:
        continue
    for j in range(2 * a, MAX, a):
        cnt[j] = 0
res = 0
for a in A:
    if cnt[a] == 1:
        res += 1
print(res)

### FIXED CODE ###

MAX = 10 ** 6 + 1
N = int(input())
A = list(map(int, input().split()))
cnt = [0] * MAX
f = [True] * MAX
for a in A:
    cnt[a] += 1
    if not f[a] or cnt[a] > 1:
        continue
    for j in range(2 * a, MAX, a):
        f[j] = False
res = 0
for a in A:
    if f[a] and cnt[a] == 1:
        res += 1
print(res)
### BUGGY CODE ###

def calcdp(i, s):
    # i番目の男性まで評価しときに、女性のマッチング状態がsとなる組み合わせの数
    global dp, MOD, N, A
    if dp[i][s] != -1:
        return dp[i][s]
    
    r = 0
    for j in range(N):
        if A[i-1][j] and s & (1 << j):
            r += calcdp(i - 1, s ^ (1 << j))
    
    r = r % MOD
    dp[i][s] = r
    return r


N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
MOD = 10**9 + 7

dp = [[-1] * 2**N for _ in range(N+1)]
dp[0][0] = 1

print(calcdp(N, 2**N-1))


                

### FIXED CODE ###

def calcdp(i, s):
    # i番目の男性まで評価しときに、女性のマッチング状態がsとなる組み合わせの数
    global dp, MOD, N, A
    if dp[i][s] != -1:
        return dp[i][s]
    
    r = 0
    for j in range(N):
        if A[i-1][j] and s & (1 << j):
            r += calcdp(i - 1, s ^ (1 << j))
    
    dp[i][s] = r = r % MOD
    return r


N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
MOD = 10**9 + 7

dp = [[-1] * 2**N for _ in range(N+1)]
dp[0][0] = 1

print(calcdp(N, 2**N-1))
### BUGGY CODE ###

n=int(input())
l=input().split()
q=[]
f=1
for i in l:
  if i not in q:
    q.append(i)
  else:
    f=0
    break
if f==1:
  print('YES')
else:
  print('NO')



### FIXED CODE ###

n=int(input())
l=input().split()
l.sort()
flag=1
for i in range(n-1):
  if l[i]==l[i+1]:flag=0
if flag==1:print("YES")
else:print("NO")
### BUGGY CODE ###

cou = int(input())
bars = input().split()
two = [0, 0]
i = 0
ca = len(bars)
while i < ca:
    if bars[i] in two:
        pass
    else:
      now = bars[i]
      if bars.count(now) > 3:
          two.extend(now)
          two.extend(now)
      elif bars.count(now) > 1:
          two.extend(now)
      else:
          pass
    i += 1
two.sort(key=int)
ans = int(two[-1]) * int(two[-2])
print(ans)


### FIXED CODE ###

n=input()
a = list(map(int, input().split()))
a.sort()
h, w =0, 0
while True:
    try:
        if a[-1] == a[-2]:
            h = a[-1]
            a.pop()
            a.pop()
            break
        else:
            a.pop()
    except:
        break

while True:
    try:
        if a[-1] == a[-2]:
            w = a[-1]
            a.pop()
            a.pop()
            break
        else:
            a.pop()
    except:
        break
print(h*w)
### BUGGY CODE ###

H,N = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N)]
INF = float("inf")
dp0 = [INF]*(H+1)
dp1 = [INF]*(H+1)
dp0[0] = 0
for i in range(N):
    a,b = AB[i]
    dp1[H] = dp0[H]
    for h in range(H-1, -1, -1):
        dp1[h] = min(dp0[h], dp1[h+1])
    assert dp1[0] == 0
    for h in range(H+1):
        dp1[h] = min(dp1[h], dp1[max(h-a,0)]+b)
    t = dp1
    dp1 = dp0
    dp0 = t
print(dp0[H])

### FIXED CODE ###

H,N = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N)]
INF = float("inf")
dp0 = [INF]*(H+1)
dp1 = [0]*(H+1)
dp0[0] = 0
for i in range(N):
    a,b = AB[i]
    dp1[H] = dp0[H]
    for h in range(H-1, -1, -1):
        dp1[h] = min(dp0[h], dp1[h+1])
    for h in range(H+1):
        dp1[h] = min(dp1[h], dp1[max(h-a,0)]+b)
    t = dp1
    dp1 = dp0
    dp0 = t
print(dp0[H])
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0
for key in range(n):
    cnt = True
    for i in range(key+1):
        if p[i]<p[key]:
            cnt = False
    if cnt:
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
#ans = 0
#for key in range(n):
#    cnt = True
#    for i in range(key+1):
#        if p[i]<p[key]:
#            cnt = False
#    if cnt:
#        ans += 1
#print(ans)

ans = 0
min_left = 2 * 10**5
for i in range(n):
    min_left = min(min_left,p[i])
    if min_left >= p[i]:
        ans += 1
print(ans)
### BUGGY CODE ###

N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        r[i][j] = r[i][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
    print(q)

### FIXED CODE ###

N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if i == 0:
            r[i][j] = p[i][j] + r[i][j-1]      
        elif j == 0:
            r[i][j] = p[i][j] +r[i-1][j]
        else:
            r[i][j] = r[i-1][j] + r[i][j-1] - r[i-1][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    if Qlist[i][0] == 1:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1]
    else:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1] - r[Qlist[i][0]-2][Qlist[i][1]-1]
    print(b)
### BUGGY CODE ###

import sys

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i, row in enumerate(field, start=1):
    for j, c in enumerate(row, start=1):
        l[i][j] = l[i][j - 1] + 1 if c == '.' else 0
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
for i, row in reversed(list(enumerate(field, start=1))):
    for j, c in reversed(list(enumerate(row, start=1))):
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        r[i][j] = r[i][j + 1] + 1 if c == '.' else 0


ans = 0
for ll, rr, uu, dd in zip(l, r, u, d):
    ans = max(ans, max(map(sum, zip(ll, rr, uu, dd))))
print(ans - 3)


### FIXED CODE ###

import sys

h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]

l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]

for i in range(1, h + 1):
    fi = field[i - 1]
    li = l[i]
    for j in range(1, w + 1):
        c = fi[j - 1]
        u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
        li[j] = li[j - 1] + 1 if c == '.' else 0
for i in range(h, 0, -1):
    fi = field[i - 1]
    ri = r[i]
    for j in range(w, 0, -1):
        c = fi[j - 1]
        d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
        ri[j] = ri[j + 1] + 1 if c == '.' else 0

ans = 0
for i in range(1, h + 1):
    li, ri, ui, di = l[i], r[i], u[i], d[i]
    ans = max(ans, max(li[j] + ri[j] + ui[j] + di[j] for j in range(1, w + 1)))
print(ans - 3)
### BUGGY CODE ###

def main():
  n = int(input())
  S = input()
  ans = 0
  dp = [0]*(n*n)
  for j in range(n-1, 0, -1):
    for i in range(j-1, -1, -1):
      if j == n-1:
        dp[i*n+j] = int(S[i] == S[j])
      else:
        if S[i] == S[j]:
          dp[i*n+j] = dp[i*n+j+1+n] + 1
      ans = max(ans, min(dp[i*n+j], j-i))
  print(ans)
if __name__ == "__main__":
  main()

### FIXED CODE ###

def z_algo(S):
    N = len(S)
    A = [0]*N
    A[0] = N
    i, j = 1, 0
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        A[i] = j
        if not j:
            i += 1
            continue
        k = 1
        while i+k < N and k+A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

n = int(input())
s = input()
ans = 0
for i in range(n):
  A = z_algo(s[i:])
  for j in range(1, n-i):
    m = min(j, A[j])
    ans = max(m, ans)
print(ans)
### BUGGY CODE ###

N = int(input())
E = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
K = 0
E_sorted = sorted(E, key=lambda x:x[0])
ans = {}
V = [[] for _ in range(N)]
for e in E_sorted:
  a, b = e
  c = 1
  req_K = True
  for i in range(1, K+1):
    if not (i in V[a]):
      c = i
      req_K = False
      break
  if req_K:
    K += 1
    c = K
  V[a].append(c)
  V[b].append(c)
  ans[e] = c
print(K)
for e in E:
  print(ans[e])


### FIXED CODE ###

from collections import OrderedDict
N = int(input())
color_parents = [0] * N
tree = [[] for _ in range(N)]
color = OrderedDict()
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  color[(a, b)] = 0
for a in range(N):
  c_p = color_parents[a]
  c = 1
  for b in tree[a]:
    if c == c_p:
      c += 1
    color[(a, b)] = c
    color_parents[b] = c
    c += 1
print(max(color.values()))
for k in color.keys():
  print(color[k])
### BUGGY CODE ###

import sys
from math import *
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
li = []
ct = 0
for i in range(n):
    #li.append("".join(sorted(input())))
    li.append(sorted(input()))
for i in range(n):
    for j in range(i+1, n):
        if li[i] == li[j]:
            ct += 1
print(ct)





### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
li = []
ct = 0
su = 0
alpha2num = lambda c: ord(c) - ord('a') + 1
for i in range(n):
    su = 0
    li.append("".join(sorted(input())))

lll= 1
list.sort(li)
li.append("a")
for i in range(n):

    if li[i] == li[i+1]:
        lll += 1
    else:
        if lll != 1:
            for j in range(1, lll):
                ct += j
        lll = 1
print(ct)
### BUGGY CODE ###

import sys
import math


def is_prime(N):
    if N == 1:
        return False
    i = 2
    while i * i <= N:
        if N % i == 0:
            return False
        i += 1
    return True


def main():
    N = int(input())
    if N == 1:
        print(0)
        sys.exit()
    if is_prime(N):
        print(1)
        sys.exit()
    else:
        count = 0
        for i in range(2, N):
            if N < i:
                break
            if N % i == 0:
                if is_prime(i):
                    count += 1
                    N //= i
                else:
                    j = 2
                    while i % j != 0:
                        j += 1
                    now = i
                    while now > j:
                        now /= j
                        if now == j:
                            count += 1
                            N //= i
        print(count)

if __name__ == '__main__':
     main()



### FIXED CODE ###

import sys
import math


def is_prime(N):
    if N == 1:
        return False
    i = 2
    while i * i <= N:
        if N % i == 0:
            return False
        i += 1
    return True

def prime(N):
    prime = []
    is_prime = []  # 全て素数であると初期化
    for i in range(N):
        if i * i > N:
            break
        is_prime.append(True)
    is_prime[0] = is_prime[1] = False # 0,1は素数ではない
    n = len(is_prime)
    for i in range(2, n):
        if is_prime[i]:
            # iは素数である
            prime.append(i)
            for j in range(2 * i, n, i):
                # iの倍数は素数でない
                is_prime[j] = False
    # N以下の素数を表示
    return prime, n

def main():
    N = int(input())
    if N == 1:
        print(0)
    else:
        if is_prime(N):
            print(1)
        else:
            prime_list, n = prime(N)
            used = []
            prime_exponentiation = []
            count = 0
            for i in range(len(prime_list)):
                now = prime_list[i]
                j = 1
                while now ** j <= N:
                    prime_exponentiation.append(now ** j)
                    j += 1
            prime_exponentiation.sort()
            for i in range(len(prime_exponentiation)):
                now = prime_exponentiation[i]
                if N < now:
                    j = 0
                    while not is_prime(N):
                        if N == 1:
                            break
                        while N % prime_list[j] == 0:
                            N //= prime_list[j]
                        j += 1 
                    break
                if N % now == 0:
                    count += 1
                    used.append(now)
                    N //= now
            if N not in used and N != 1:
                count += 1
            print(count)


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

N, M = map(int, input().split())
tmp = input().split(' ')
H = []
for i in range(N):
    H = H + [int(tmp[i])]

A = []
B = []
for i in range(M):
    ta, tb = map(int, input().split())
    A = A + [ta]
    B = B + [tb]

ans = [0]*N
# v: 0ならいい展望台、1なら良くない展望台 
for i in range(N):
    j = 0
    while(ans[i] == 0 and j<M):
        if A[j]-1 == i:
            if H[B[j]-1] >= H[i]:
                ans[i] = 1
            else:
                ans[B[j]-1] = 1
        if B[j]-1 == i:
            if H[A[j]-1] >= H[i]:
                ans[i] = 1
            else:
                ans[A[j]-1] = 1
        j += 1

print(ans.count(0))

### FIXED CODE ###

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

A = [0]*M
B = [0]*M
for i in range(M):
    ta, tb = map(int, input().split())
    A[i] = ta - 1
    B[i] = tb - 1

ans = [True]*N
# v: Trueならいい展望台、Falseなら良くない展望台 
for i in range(M):
    ans[A[i]] = H[A[i]] > H[B[i]] and ans[A[i]]
    ans[B[i]] = H[B[i]] > H[A[i]] and ans[B[i]]

print(ans.count(True))
### BUGGY CODE ###


def get_coord(num, H, W, masu):
    for i in range(H):
        for j in range(W):
            if masu[i][j] == num:
                return i, j

H, W, D = map(int, input().split())
masu = []
for i in range(H):
    masu.append([int(i) for i in input().split()])
Q = int(input())

exam = []
for i in range(Q):
    exam.append([int(i) for i in input().split()])

for i in range(Q):
    reduce_MP = 0
    num = exam[i][0]
    coord1 = get_coord(num, H, W, masu)
    while num < exam[i][1]:
        coord2 = get_coord(num + D, H, W, masu)
        reduce_MP += abs(coord1[0] - coord2[0]) + abs(coord1[1] - coord2[1])
        num += D
        coord1 = coord2
    print(reduce_MP)



### FIXED CODE ###

H, W, D = list(map(int, input().split()))

Amap = []
for i in range(H):
    Amap.append(list(map(int, input().split())))

xx = [0 for i in range(90002)]
yy = [0 for i in range(90002)]
for y in range(H):
    for x in range(W):
        xx[Amap[y][x]] = x
        yy[Amap[y][x]] = y
Q = int(input())

coord = []
for i in range(Q):
    coord.append(list(map(int, input().split())))

# magic point calculation
mp = [0 for i in range(90002)]

for i in range(D+1, 90002):
    mp[i] = mp[i-D] + abs(xx[i] -xx[i-D]) + abs(yy[i] - yy[i-D])

for i in coord:
    print(mp[i[1]] - mp[i[0]])
### BUGGY CODE ###

from copy import deepcopy

n = int(input().strip())
a = list(map(int, input().split()))
b = deepcopy(a)
counts = {}
tmp = b[0]
for elem in b:
    if str(elem) in counts:
        counts[str(elem)] += 1
    else:
        counts[str(elem)] = 1
    if tmp != elem:
        tmp = elem
c = deepcopy(counts)
for k, v in counts.items():
    c[k] = v * (v - 1) // 2
for elem in a:
    print(sum(c.values()) - c[str(elem)] + ((counts[str(elem)] - 1) * (counts[str(elem)] - 2) // 2))


### FIXED CODE ###

from copy import deepcopy

n = int(input().strip())
a = list(input().split())
b = deepcopy(a)
counts = {}
tmp = b[0]
for elem in b:
    if elem in counts:
        counts[elem] += 1
    else:
        counts[elem] = 1
    if tmp != elem:
        tmp = elem
c = deepcopy(counts)
for k, v in counts.items():
    c[k] = v * (v - 1) // 2
su = sum(c.values())
for elem in a:
    print(su - c[elem] + ((counts[elem] - 1) * (counts[elem] - 2) // 2))
### BUGGY CODE ###

s = input()
a = int(s)%2019
mod_N = [0]*2019
mod_N[a] += 1
r = 10**(len(s)-1)
for i in range(len(s)):
  a = (a-int(s[i])*10**r)%2019
  r = r//10
  mod_N[a] += 1
ans = 0
for i in mod_N:
  ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

from collections import deque

s = list(input())
q = int(input())
s = deque(s)

fc = []
for i in range(q):
    t, *f = map(str, input().split())
    if t == "1":
        s.reverse()
    else:
        if f[0] == "1":
            s.appendleft(f[1])
        else:
            s.append(f[1])

print("".join(s))

### FIXED CODE ###

from collections import deque

s = list(input())
q = int(input())
s = deque(s)

flg = "order"
for i in range(q):
    t, *f = map(str, input().split())
    if t == "1":
        if flg == "order":
            flg = "reverse"
        else:
            flg = "order"
    else:
        if f[0] == "1":
            if flg == "order":
                s.appendleft(f[1])
            else:
                s.append(f[1])
        else:
            if flg == "order":
                s.append(f[1])
            else:
                s.appendleft(f[1])

if flg == "order":
    print("".join(s))
else:
    s.reverse()
    print("".join(s))
### BUGGY CODE ###

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

L.sort()
ans = 0
for i in range(N):
    for j in range(i+1, N):
        lower_bound = bisect.bisect_left(L, L[i]+L[j])
        for k in range(lower_bound):
            if k == i or k == j:
                continue
            if L[i]+L[j] > L[k] and L[i]+L[k] > L[j] and L[j]+L[k] > L[i]:
                ans += 1
        # print(L[i], L[j])
        # print(bisect.bisect_left(L, L[i]+L[j])-2)
        # ans += max(bisect.bisect_left(L, L[i]+L[j])-2, 0)
print(ans//3)


### FIXED CODE ###

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

L.sort()
ans = 0
for i in range(N):
    for j in range(i+1, N):
        lower_bound_i_plus_j = bisect.bisect_left(L, L[i]+L[j])
        ans += lower_bound_i_plus_j - (j+1)

print(ans)