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

#!/snap/bin/pypy3
import sys

MEMO = dict()

def search(n, data):
    global MEMO

    if n in MEMO:
        return MEMO[n]
    else:
        if not n in data:
            MEMO[n] = 0
            return 0

        MEMO[n] = max(search(i, data) for i in data[n]) + 1
        return MEMO[n]


def main():
    sys.setrecursionlimit(65535)
    N, M = map(int, input().split())
    data = dict()
    for _ in range(M):
        x, y = map(int, input().split())
        if x not in data:
            data[x] = [y]
        else:
            data[x].append(y)

    print(max(search(n, data) for n in range(1, N+1)))



if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python3
import sys

MEMO = dict()

def search(n, data):
    global MEMO

    if n in MEMO:
        return MEMO[n]
    else:
        if not n in data:
            MEMO[n] = 0
            return 0

        MEMO[n] = max(search(i, data) for i in data[n]) + 1
        return MEMO[n]


def main():
    # sys.setrecursionlimit(65535)
    sys.setrecursionlimit(10**9)
    N, M = map(int, input().split())
    data = dict()
    for _ in range(M):
        x, y = map(int, input().split())
        if x not in data:
            data[x] = [y]
        else:
            data[x].append(y)

    print(max(search(n, data) for n in range(1, N+1)))



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

n = int(input())
sum = 0

for i in range(1,n):
  sum += i
  
print(sum)

### FIXED CODE ###

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

n,k = map(int,input().split())
h = [int(input()) for _ in range(n)]
h.sort()
sa = 10**10
for i in range(n-k+1):
    s = h[i:i+k]
    sa = min(sa,s[-1]-s[0])
print(sa)

### FIXED CODE ###

from sys import stdin
from itertools import groupby

n,k = [int(x) for x in stdin.readline().rstrip().split()]
li = [int(stdin.readline().rstrip()) for _ in range(n)]
li.sort()

mi = 10**10
for i in range(n-k+1):
    mi = min(mi,li[i+k-1]-li[i])

print(mi)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    edges = defaultdict(list)
    for _ in range(N):
        x, y = LI()
        edges[x].append(-y)
        edges[-y].append(x)
    visited = defaultdict(int)
    ans = -N
    for node in edges:
        if not visited[node]:
            li = solve(node, edges, visited)
            m, p = 0, 0
            for z in li:
                if z < 0:
                    m += 1
                else:
                    p += 1
            ans += m * p
    return ans

def solve(v, edges, visited):
    visited[v] = 1
    ret = [v]
    for u in edges[v]:
        if not visited[u]:
            ret += solve(u, edges, visited)
    return ret

print(main())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0:  # merge
            if gx == gy:
                continue
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy < 0:
                m += 1
            else:
                p += 1
        ans += m * p
    return ans

print(main())
### BUGGY CODE ###

def bit_add(arr, n, i, x):
    while i <= n:
        arr[i] += x
        i += i & -i

def bit_sum(arr, i):
    result = 0
    while i > 0:
        result += arr[i]
        i ^= i & -i
    return result

n, q = map(int, input().split())
color = [int(i) for i in input().split()]
query = []
rli = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    query.append((l, r))
    rli[i] = (r << 40) + (l << 20) + i
rli.sort()
mask = (1 << 20) - 1
bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0

for j in range(q):
    k = rli[j]
    r = k >> 40
    l = (k >> 20) & mask
    i = k & mask
    while p < r:
        c = color[p]
        before_appeared = appeared[c]
        if before_appeared != -1:
            bit_add(bit, bn, before_appeared + 2, -1)
        bit_add(bit, bn, p + 2, 1)
        appeared[c] = p
        p += 1
    ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, l)
print('\n'.join(map(str, ans)))    

### FIXED CODE ###

def bit_add(arr, n, i, x):
    while i <= n:
        arr[i] += x
        i += i & -i

def bit_sum(arr, i):
    result = 0
    while i > 0:
        result += arr[i]
        i ^= i & -i
    return result

n, q = map(int, input().split())
color = [int(i) for i in input().split()]
query = []
rli = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    query.append((l, r))
    rli[i] = (r << 40) + (l << 20) + i
rli.sort()
mask = (1 << 20) - 1
bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0

for j in range(q):
    k = rli[j]
    r = k >> 40
    l = (k >> 20) & mask
    i = k & mask
    while p < r:
        c = color[p]
        before_appeared = appeared[c]
        if before_appeared != -1:
            bit_add(bit, bn, before_appeared + 2, -1)
        bit_add(bit, bn, p + 2, 1)
        appeared[c] = p
        p += 1
    ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, l)
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from collections import Counter

    N = int(input())
    A = list(map(int, input().split()))
    CA = Counter(A)
    Q = int(input())
    for i in range(Q):
        b, c = map(int, input().split())
        CA[c] += CA[b]
        CA[b] = 0
        sumA = 0
        for key, value in CA.items():
            sumA += key*value
        print(sumA)

main()

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from collections import Counter

    N = int(input())
    A = list(map(int, input().split()))
    CA = Counter(A)
    sumA = 0
    for key, value in CA.items():
        sumA += key*value

    Q = int(input())
    for i in range(Q):
        b, c = map(int, input().split())
        sumA += (c-b)*CA[b]
        CA[c] += CA[b]
        CA[b] = 0
        print(sumA)

main()
### 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()))
ABlist = []
ABClist = []

for x in A:
    for y in B:
        sumple = x + y
        ABlist.append(sumple)
        ABlist.sort(reverse=True)
        ABlist = ABlist[:K]

for x in ABlist:
    for z in C:
        test = x + z
        ABClist.append(test)
        ABClist.sort(reverse=True)
        ABClist = ABClist[:K]

for x in ABClist:
    print(x)

### 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()))
ABlist = []
ABClist = []

for x in A:
    for y in B:
        sumple = x + y
        ABlist.append(sumple)
    ABlist.sort(reverse=True)
    ABlist = ABlist[:K]

for x in ABlist:
    for z in C:
        test = x + z
        ABClist.append(test)
    ABClist.sort(reverse=True)
    ABClist = ABClist[:K]

for x in ABClist:
    print(x)
### BUGGY CODE ###

from operator import itemgetter
N, M = map(int, input().split())
ab = []
for i in range(M):
    a,b = map(int, input().split())
    ab.append((a,b))

fl = False
for i,j in ab:
    if i!=1:
        continue
    for k,l in ab:
        if i==1 and (j!=k or l!=N):
            continue
        else:
            fl = True
print('POSSIBLE') if fl else print('IMPOSSIBLE')

### FIXED CODE ###

from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(list)
for i in range(M):
    a,b = map(int, input().split())
    d[a].append(b)

for i,j in list(d.items()):
    if i!=1:
        continue
    for k in j:
        if N in d[k]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
S = 0
MOD = 1000000007

for i in range(N - 1):
    for j in range(i + 1, N):
        S += A[i] ^ A[j]

print(S % MOD)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
MOD = 10 ** 9 + 7
ans = 0

for i in range(61):
    cnt = np.count_nonzero(A & 1)
    ans += (2 ** i) * cnt * (N - cnt)
    A >>= 1

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

n=int(input())
S=input()
dp=[[0]*(n+1) for _ in range(n+1)]

for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if S[i] != S[j]:
            continue
        else:
            dp[i][j] = dp[i+1][j+1] + 1

ans=0
for i in range(n):
    for j in range(n):
        if i>=j:
            continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)

print(ans)

### FIXED CODE ###

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

dp = [[0] * N for _ in range(N)]

ans = 0

for j in range(N - 1, 0, -1):
    sj = S[j]
    for i in range(j-1, -1, -1):
        si = S[i]
        if j == N - 1:
            if si == sj:
                dp[j][i] = 1
                ans = 1
        else:
            if si == sj:
                dp[j][i] = min(j - i, dp[j + 1][i + 1] + 1)
                ans = max(ans, dp[j][i])

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

import sys
dp = { 0:0, 1:1, 2:1 }
N = int(input())
X = sys.stdin.readline().strip()

def f(num):
    if num in dp:
        return dp[num]
    b = bin(num)
    popcount = b.count('1')
    if num % popcount == 0:
        dp[num] = 1
    else:
        dp[num] = 1 + f(num % popcount)

    return dp[num]

for i in range(0, N):
    if X[i] == '0':
        #print(X[:i] + '1' + X[i+1:])
        print(f(int(X[:i] + '1' + X[i+1:], 2)))
    else:
        #print(X[:i] + '0' + X[i+1:])
        print(f(int(X[:i] + '0' + X[i+1:], 2)))

### FIXED CODE ###

import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt

def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

#nX = int(X, 2)
pcnt = X.count('1')
MOD1 = pcnt + 1
MOD2 = pcnt - 1

nXp = 0
nXm = 0

pow1 = [1] * N
pow2 = [0] * N
for i in range(1, N):
    pow1[i] = (pow1[i-1] * 2) % MOD1
if MOD2 != 0:
    pow2[0] = 1
    for i in range(1, N):
        pow2[i] = (pow2[i-1] * 2) % MOD2

for i in range(N):
    if X[i] == '1':
        nXp += pow1[N-1-i]
nXp %= MOD1

if MOD2 != 0:
    for i in range(N):
        if X[i] == '1':
            nXm += pow2[N-1-i]

    nXm %= MOD2
    

for i in range(0, N):
    if X[i] == '0':
        k = (nXp + pow1[N-1-i]) % MOD1
        print(f(k) + 1)
    else:
        if MOD2 == 0:
            print(0)
        else:
            k = (nXm - pow2[N-1-i]) % MOD2
            print(f(k) + 1)
### BUGGY CODE ###

def main():
    n, k= map(int, input().split())
    lis = list(map(int, input().split()))
    dp = []
    tmp = []
    for _ in range(n+1):
        dp.append(0)

    for i in range(2, k+1):
        if i <= n:
            dp[i] = abs(lis[i-1] - lis[0])
        # print(i, dp[i])
    #print("start")
    for i in range(k+1, n+1):
        for t in range(1, k+1):
            cost_t = abs(lis[i-1] - lis[i-1 - t]) + dp[i-t]
            tmp.append(cost_t)
        dp[i] = min(tmp)
        tmp = []
        #print(i, dp[i])
    print(dp[n])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k= map(int, input().split())
    lis = list(map(int, input().split()))
    dp = []
    tmp = []
    for _ in range(n+1):
        dp.append(0)

    for i in range(2, k+1):
        if i <= n:
            dp[i] = abs(lis[i-1] - lis[0])
        # print(i, dp[i])
    #print("start")
    for i in range(k+1, n+1):
        for t in range(1, k+1):
            cost_t = abs(lis[i-1] - lis[i-1 - t]) + dp[i-t]
            tmp.append(cost_t)
        dp[i] = min(tmp)
        tmp = []
        #print(i, dp[i])
    print(dp[n])

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

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N = int(input())
    A = list(map(int, input().split()))
    M = 60
    bitcnt = [0] * M
    for a in A:
        for i in range(M):
            if a & (1 << i):
                bitcnt[i] += 1
    ans = 0
    for a in A:
        for i in range(M):
            if a & (1 << i):
                ans = (ans + (1 << i) * (N - bitcnt[i])) % MOD
            else:
                ans = (ans + (1 << i) * bitcnt[i]) % MOD
            ans %= MOD
    ans = div(ans, 2)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N = int(input())
    A = list(map(int, input().split()))
    M = 60
    bitcnt = [0] * M
    for a in A:
        for i in range(M):
            if a & (1 << i):
                bitcnt[i] += 1
    ans = 0
    for a in A:
        for i in range(M):
            x = 1 << i
            if a & x:
                ans = (ans + x * (N - bitcnt[i])) % MOD
            else:
                ans = (ans + x * bitcnt[i]) % MOD
    ans = div(ans, 2)
    print(ans)


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

N, M, Q = map(int, input().split())
city = [[0] * (N+1) for i in range(N+1)]
for i in range(M):
  l, r = map(int, input().split())
  city[l][r] += 1

for i in range(N+1):
  for j in range(N):
    city[i][j+1] += city[i][j]

for i in range(Q):
  p, q = map(int, input().split())
  print(sum([city[j][q] - city[j][p-1] for j in range(p, q+1)]))

### FIXED CODE ###

N, M, Q = map(int, input().split())
city = [[0] * (N+1) for i in range(N+1)]
for i in range(M):
  l, r = map(int, input().split())
  city[l][r] += 1

for i in range(N+1):
  for j in range(N):
    city[i][j+1] += city[i][j]

for i in range(N+1):
  for j in range(N):
    city[j+1][i] += city[j][i]

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

N, X = map(int, input().split())
x = list(map(int, input().split()))

y = [x[0]]
for i in range(N-1):
    x[i+1] += x[i]
    y.append(x[i+1])

ans = 10**21
for k in range(1, N+1):
    num = N
    memo = k * X + X * N
    i = 0
    while num > k:
        memo += max(i+3, 5) * (y[num-1] - y[num-1-k])
        num -= k
        i += 2
    memo += max(i+3, 5) * (y[num-1])
    ans = min(ans, memo)

print(ans)

### FIXED CODE ###

N, X = map(int, input().split())
x = list(map(int, input().split()))

y = [x[0]]
for i in range(N-1):
    x[i+1] += x[i]
    y.append(x[i+1])

ans = 10**21
for k in range(1, N+1):
    num = N
    memo = k * X + X * N
    i = 0
    while num > k:
        memo += max(i+3, 5) * (y[num-1] - y[num-1-k])
        num -= k
        i += 2
    memo += max(i+3, 5) * (y[num-1])
    ans = min(ans, memo)

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

rn,gn,bn,n=map(int,input().split())
nn=sorted([rn,gn,bn]) 
print(sum(n-nn[0]*r-nn[1]*g >=0 and (n-nn[0]*r-nn[1]*g)%nn[2]==0 for r in range(1+n//nn[0]) for g in range(1+n//nn[1])))

### FIXED CODE ###

rn,gn,bn,n=map(int,input().split())
nn=sorted([rn,gn,bn]) 
c=0
for r in range(1+n//nn[0]):
    rt=n-nn[0]*r
    for g in range(1+rt//nn[1]):
        gt=rt-nn[1]*g
        if gt%nn[2]==0:
            c+=1
print(c)
### BUGGY CODE ###

#input
H, W = map(int, input().split())
import numpy as np
S = np.array([input() for _ in range(H)])

#output
import numpy as np
from collections import deque
INF = -1
dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

def clear_maze(sx, sy, gx, gy, maze):
    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dp[sx, sy] = 0

        while len(q):
            x, y = q.pop()

            if x == gx and y == gy:
                break

            for i in range(0, 4):
                nx, ny = x + dx[i], y + dy[i]

                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and dp[nx, ny] == INF:
                    q.insert(0, (nx, ny))
                    dp[nx, ny] = dp[x, y] + 1
        return dp[gx, gy]
    return bfs()

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            dp = np.full((H, W), INF)
            q = []
            q.insert(0, (i, j))
            dp[i, j] = 0
            while len(q):
                x, y = q.pop()

                for t in range(4):
                    nx, ny = x + dx[t], y + dy[t]

                    if (0 <= nx < H) and (0 <= ny < W) and (S[nx][ny] != "#") and (dp[nx, ny] == INF):
                        q.insert(0, (nx, ny))
                        dp[nx, ny] = dp[x, y] + 1
            for row in dp:
                answer = max(answer, max(row))
print(int(answer))

### FIXED CODE ###

#input
H, W = map(int, input().split())
import numpy as np
S = [input() for _ in range(H)]

#output
import numpy as np

INF = -1
dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            dp = np.full((H, W), INF)
            q = []
            q.insert(0, (i, j))
            dp[i, j] = 0
            while len(q):
                x, y = q.pop()

                for t in range(4):
                    nx, ny = x + dx[t], y + dy[t]

                    if (0 <= nx < H) and (0 <= ny < W) and (S[nx][ny] != "#") and (dp[nx, ny] == INF):
                        q.insert(0, (nx, ny))
                        dp[nx, ny] = dp[x, y] + 1
            for row in dp:
                answer = max(answer, max(row))
print(int(answer))
### BUGGY CODE ###


def main():
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[None]*n
    temp=[1001]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        low=i-k-1
        if low<0:
            low=-1
        for j in range(i-1,low,-1):
            temp[j]=dp[j]+abs(h[i]-h[j])

        # temp2=dp[i-2]+abs(h[i]-h[i-2])
        # temp1=dp[i-1]+abs(h[i]-h[i-1])
        dp[i]=min(temp)
        temp=[1001]*n
    print(dp[n-1])

if __name__=='__main__':
    main()


### FIXED CODE ###


def main():
    n,k=map(int,input().split())
    h=list(map(int,input().split()))
    dp=[None]*n
    temp=[1001]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        low=i-k-1
        if low<0:
            low=-1
        for j in range(i-1,low,-1):
            temp[j]=dp[j]+abs(h[i]-h[j])
            if j==i-1:
                mn=temp[j]
            else:
                if mn > temp[j]:
                    mn=temp[j]
        # temp2=dp[i-2]+abs(h[i]-h[i-2])
        # temp1=dp[i-1]+abs(h[i]-h[i-1])
        dp[i]=mn
        #temp=[1001]*n
    print(dp[n-1])

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

import sys
from itertools import product


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = input()
    r = []
    g = []
    b = []
    for i in range(N):
        if S[i] == "R":
            r.append(i)
        elif S[i] == "G":
            g.append(i)
        else:
            b.append(i)
    A = product(r, g, b)
    ans = 0
    for a in A:
        a = list(a)
        x = abs(a[0] - a[1])
        y = abs(a[1] - a[2])
        z = abs(a[0] - a[2])
        if x != y and y != z and z != x:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import Counter


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = input()
    C = Counter(S)
    R = C.get("R", 0)
    G = C.get("G", 0)
    B = C.get("B", 0)
    ans = R * G * B
    for left in range(N):
        for mid in range(left + 1, N):
            right = mid + mid - left
            if right < N:
                if S[right] != S[mid] and S[mid] != S[left] and S[right] != S[left]:
                    ans -= 1
    print(ans)


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

import sys
input = sys.stdin.readline

import numpy as np

def main():
  n, k = map(int, input().split())
  A = np.array(sorted(list(map(int, input().split()))))
  F = np.array(sorted(list(map(int, input().split())), reverse=True))
  def is_time(x):
    c = 0
    for i in range(n):
      c = np.maximum(A - x//F, 0).sum()
    if c <= k:
      return True
    return False
  ng = -1
  ok = max(A*F)
  while ok - ng > 1:
    m = (ng + ok)//2
    if is_time(m):
      ok = m
    else:
      ng = m
  print(ok)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

n, k = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())))[::-1]
def is_time(x):
  c = 0
  for i in range(n):
    c += max(0, A[i] - x//F[i])
  if c <= k:
    return True
  return False
ng = -1
ok = 0
for i in range(n):
  ok = max(ok, A[i]*F[i])
while ok - ng > 1:
  m = (ng + ok)//2
  if is_time(m):
    ok = m
  else:
    ng = m
print(ok)
### BUGGY CODE ###

N,X=map(int,input().split())
x=list(map(int,input().split()))
x.append(X)
x=list(map(lambda t:t-min(x),x))
def gcd(a,b):
    while b:
        a,b=b,a%b
    return(a)
a=10**10
for i,j in zip(x,x[1:]):
    a=min(a,gcd(i,j))
print(a)

### FIXED CODE ###

N,X=map(int,input().split())
x=list(map(int,input().split()))
x.append(X)
mx=min(x)
x=list(map(lambda t:t-mx,x))
def gcd(a,b):
    while b:
        a,b=b,a%b
    return(a)
a=10**10
for i,j in zip(x,x[1:]):
    a=min(a,gcd(i,j))
print(a)
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
*A, = map(int, input().split())
indices = {a: i for i, a in enumerate(A)}
seen_idx = [-1, N]
ans = 0
for a in range(1, N+1):
    idx = indices[a]
    t = bisect_left(seen_idx, idx)
    seen_idx.insert(t, idx)
    left = idx - seen_idx[t-1]
    right = seen_idx[t+1] - idx
    ans += left * right * a
print(ans)

### FIXED CODE ###

N = int(input())
*A, = map(int, input().split())
indices = {a: i for i, a in enumerate(A)}
left = {i: i for i in range(N)} # "left[i] = l" is equivalent to "A[l], ..., A[i-1] > A[i]"
right = {i: i for i in range(N)} # "right[i] = r" is equivalent to "A[i] < A[i+1], ..., A[r]"
ans = 0
for a in range(N, 0, -1):
    idx = indices[a]
    l, r = left[idx], right[idx]
    ans += (idx - l + 1) * (r - idx + 1) * a
    left[r+1], right[l-1] = l, r # A[l-1] < A[l], ..., A[r] > A[r+1]
print(ans)