Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd

n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
lcm = aaa[0]
for a in aaa[1:]:
    lcm = lcm * a // gcd(lcm, a)

ans = 0
for a in aaa:
    ans = (ans + lcm // a) % MOD
print(ans)


Fixed submission:
def prime_factorize(n):
    i = 2
    res = {}
    while i * i <= n:
        if n % i != 0:
            i += 1
            continue
        res[i] = 0
        while n % i == 0:
            res[i] += 1
            n //= i
        i += 1
    if n != 1:
        res[n] = 1
    return res


n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
lcm_ppf = prime_factorize(aaa[0])
for a in aaa[1:]:
    for p, c in prime_factorize(a).items():
        if p in lcm_ppf:
            lcm_ppf[p] = max(lcm_ppf[p], c)
        else:
            lcm_ppf[p] = c

lcm = 1
for p, c in lcm_ppf.items():
    lcm = lcm * pow(p, c, MOD) % MOD
# print(lcm)

ans = 0
for a in aaa:
    ra = pow(a, MOD - 2, MOD)
    ans = (ans + lcm * ra) % MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


n = int(input())
xxx = list(map(int, input().split()))
MOD = 10 ** 9 + 7
factorials, invs = prepare(n, MOD)

# print(factorials)
# print(invs)

ans = 0
dp = [0]
for i in range(n - 1):
    y = xxx[i + 1] - xxx[i]
    tmp = 0
    for k in range(i + 1):
        # print(' ', k, (dp[k] + factorials[k]) * invs[k])
        tmp = (tmp + (dp[k] + factorials[k]) * invs[k]) % MOD
    tmp = tmp * factorials[i] % MOD
    dp.append(tmp)
    # print(dp)
    ans = (ans + y * tmp * invs[i + 1]) % MOD
    # print(i, y, tmp, tmp * invs[i + 1] * factorials[n - 1] % MOD)
ans = ans * factorials[n - 1] % MOD
print(ans)


Fixed submission:
import sys


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


n = int(input())
xxx = list(map(int, input().split()))
MOD = 10 ** 9 + 7
factorials, invs = prepare(n, MOD)

ans = 0
dp = 1
for i in range(n - 1):
    cur = dp * factorials[i] % MOD
    ans = (ans + (xxx[i + 1] - xxx[i]) * cur * invs[i + 1]) % MOD
    dp = (dp + (cur + factorials[i + 1]) * invs[i + 1]) % MOD
ans = ans * factorials[n - 1] % MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

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

coef = np.minimum(np.arange(n, 1, -1), np.arange(1, n))
dp = np.zeros(n, dtype=np.int64)
dp[0] = 1
for c in coef:
    w = np.zeros(n, dtype=np.int64)
    w[::c] = 1
    dp = np.convolve(dp, w, mode='full')[:n] % m

print((dp * np.arange(n, 0, -1) % m).sum() % m)


Fixed submission:
import numpy as np

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

coef = np.minimum(np.arange(n, 1, -1), np.arange(1, n))
dp = np.zeros(n, dtype=np.int64)
dp[0] = 1
for c in coef:
    ndp = np.zeros(n, dtype=np.int64)
    for i in range(0, n, c):
        ndp[i:] += dp[:n - i]
    dp = ndp % m

print((dp * np.arange(n, 0, -1) % m).sum() % m)
Buggy python submission (verdict: Runtime Error):
import fraction
a, b = map(int, input().split())
print(a * b // fraction.gcd(a, b))

Fixed submission:
from fractions import gcd

a, b = map(int, input().split())
print(a * b // gcd(a, b))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

h, w = list(map(int, input().split()))

field = [[None] * w for _ in range(h)]
aaa = [list(map(int, input().split())) for _ in range(h)]
bbb = [list(map(int, input().split())) for _ in range(h)]
aaa = np.array(aaa, dtype=np.int64)
bbb = np.array(bbb, dtype=np.int64)
diff = abs(aaa - bbb)

offset = 15000
can = np.zeros(30001, dtype=np.int64)
can[diff[0][0] + offset] = 1
field[0][0] = can


def merge_new_can(d, can, prev_can):
    if d == 0:
        can |= prev_can
    else:
        can[d:] |= prev_can[:-d]
        can[:-d] |= prev_can[d:]


for j in range(1, w):
    d = diff[0][j]
    prev_can = field[0][j - 1]
    can = np.zeros(30001, dtype=np.int64)
    merge_new_can(d, can, prev_can)
    field[0][j] = can

for i in range(1, h):
    d = diff[i][0]
    prev_can = field[i - 1][0]
    can = np.zeros(30001, dtype=np.int64)
    merge_new_can(d, can, prev_can)
    field[i][0] = can

for i in range(1, h):
    for j in range(1, w):
        d = diff[i][j]
        can = np.zeros(30001, dtype=np.int64)
        prev_can1 = field[i][j - 1]
        prev_can2 = field[i - 1][j]
        merge_new_can(d, can, prev_can1)
        merge_new_can(d, can, prev_can2)
        field[i][j] = can

goal = field[-1][-1]
goal[15001:] |= goal[:15000][::-1]
goal = goal[15000:]
print(np.argmax(goal))


Fixed submission:
import numpy as np

h, w = list(map(int, input().split()))

aaa = [list(map(int, input().split())) for _ in range(h)]
bbb = [list(map(int, input().split())) for _ in range(h)]
aaa = np.array(aaa, dtype=np.int8)
bbb = np.array(bbb, dtype=np.int8)
diff = abs(aaa - bbb)


def merge_new_can(d, can, prev_can):
    if d == 0:
        can |= prev_can
    else:
        can[d:] |= prev_can[:-d]
        can[:-d] |= prev_can[d:]


prev_row = [None] * w

can = np.zeros(25601, dtype=np.int8)
can[diff[0][0] + 12800] = 1
prev_row[0] = can

for j in range(1, w):
    d = diff[0][j]
    can = np.zeros(25601, dtype=np.int8)
    prev_can = prev_row[j - 1]
    merge_new_can(d, can, prev_can)
    prev_row[j] = can

for i in range(1, h):
    curr_row = [None] * w

    d = diff[i][0]
    prev_can = prev_row[0]
    can = np.zeros(25601, dtype=np.int8)
    merge_new_can(d, can, prev_can)
    curr_row[0] = can

    for j in range(1, w):
        d = diff[i][j]
        can = np.zeros(25601, dtype=np.int8)
        prev_can1 = prev_row[j]
        prev_can2 = curr_row[j - 1]
        merge_new_can(d, can, prev_can1)
        merge_new_can(d, can, prev_can2)
        curr_row[j] = can

    prev_row = curr_row

goal = prev_row[-1]
goal[12801:] |= goal[:12800][::-1]
goal = goal[12800:]
print(np.argmax(goal))
Buggy python submission (verdict: Runtime Error):
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


def solve(x, y):
    d, m = divmod(x + y, 3)
    if m != 0:
        return 0
    c = abs(d - x)

    MOD = 10 ** 9 + 7

    f, invs = prepare(d, MOD)

    return f * invs[c] * invs[d - c] % MOD


x, y = map(int, input().split())
print(solve(x, y))


Fixed submission:
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


def solve(x, y):
    d, m = divmod(x + y, 3)
    if m != 0 or x / y > 2 or y / x > 2:
        return 0
    c = abs(d - x)

    MOD = 10 ** 9 + 7
    f, invs = prepare(d, MOD)
    return f * invs[c] * invs[d - c] % MOD


x, y = map(int, input().split())
print(solve(x, y))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict

n, t = map(int, input().split())
knapsack = defaultdict(lambda: 0)
knapsack[0] = 0
tmp_ans = 0
cuisines = [tuple(map(int, line.split())) for line in sys.stdin]
cuisines.sort()
for a, b in cuisines:
    for time, satisfied in list(knapsack.items()):
        if time + a >= t:
            tmp_ans = max(tmp_ans, satisfied + b)
            continue
        knapsack[time + a] = max(knapsack[time + a], satisfied + b)

print(max(tmp_ans, max(knapsack.values())))


Fixed submission:
import sys
from collections import defaultdict

n, t = map(int, input().split())
knapsack = defaultdict(lambda: 0)
knapsack[0] = 0
tmp_ans = 0
cuisines = [tuple(map(int, line.split())) for line in sys.stdin]
cuisines.sort()
for a, b in cuisines:
    for time, satisfied in list(knapsack.items()):
        if time + a >= t:
            tmp_ans = max(tmp_ans, satisfied + b)
            continue
        knapsack[time + a] = max(knapsack[time + a], satisfied + b)

print(max(tmp_ans, max(knapsack.values())))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np


def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f = f * m % MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv = invs[m - 1] = inv * m % MOD
    invs = np.array(invs, dtype=np.int64)

    return fn, invs


n = int(input())
MOD = 998244353
fn, invs = prepare(n, MOD)

n2 = n // 2

# mul = 1
# muls = [0] * n2
# for i in range(n2):
#     mul = muls[i] = mul * 2 % MOD

# mul = 1
# muls = np.zeros(n2, dtype=np.int64)
# for i in range(n2):
#     mul = muls[i] = mul * 2 % MOD

muls = np.zeros(1, dtype=np.int64)
muls[0] = 2
while muls.size < n2:
    muls = np.append(muls, muls * muls[-1] % MOD)
muls = muls[:n2]

impossibles = invs[:n2] * invs[n:n2:-1] % MOD
impossibles = impossibles * muls % MOD
impossible = sum(list(impossibles)) % MOD * fn

print((pow(3, n, MOD) - impossible) % MOD)


Fixed submission:
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


n = int(input())
MOD = 998244353
fn, invs = prepare(n, MOD)
ans = pow(3, n, MOD)
impossible = 0
mul = 2
for i in range(n // 2):
    tmp = fn * invs[i] * invs[n - i] % MOD * mul
    impossible = (impossible + tmp) % MOD
    mul = mul * 2 % MOD
print((ans - impossible) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


n = int(input())
MOD = 998244353
fn, invs = prepare(n, MOD)
ans = pow(3, n, MOD)
impossible = 0
for i in range(n // 2):
    tmp = fn * invs[i] * invs[n - i] % MOD * pow(2, i, MOD)
    impossible = (impossible + 2 * tmp) % MOD
print((ans - impossible) % MOD)


Fixed submission:
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


n = int(input())
MOD = 998244353
fn, invs = prepare(n, MOD)
ans = pow(3, n, MOD)
impossible = 0
mul = 2
for i in range(n // 2):
    tmp = fn * invs[i] * invs[n - i] % MOD * mul
    impossible = (impossible + tmp) % MOD
    mul = mul * 2 % MOD
print((ans - impossible) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np


def solve(n, k, aaa, fff):
    aaa = np.sort(aaa)
    fff = np.sort(fff)[::-1]

    l = 0
    r = 10 ** 12 + 1
    while l < r - 1:
        m = (l + r) // 2
        req = np.clip(aaa - m // fff, 0, None).sum()
        # print(aaa, m // fff, m, req)
        if req > k:
            l = m + 1
        else:
            r = m + 1
    return l


n, k = list(map(int, input().split()))
aaa = np.array(list(map(int, input().split())), dtype=np.int64)
fff = np.array(list(map(int, input().split())), dtype=np.int64)

print(solve(n, k, aaa, fff))


Fixed submission:
import numpy as np


def solve(n, k, aaa, fff):
    aaa = np.sort(aaa)
    fff = np.sort(fff)[::-1]

    l = 0
    r = 10 ** 12
    while l <= r:
        m = (l + r) // 2
        req = np.clip(aaa - m // fff, 0, None).sum()
        # print(aaa, m // fff, m, req)
        if req > k:
            l = m + 1
        else:
            r = m - 1
    return l


n, k = list(map(int, input().split()))
aaa = np.array(list(map(int, input().split())), dtype=np.int64)
fff = np.array(list(map(int, input().split())), dtype=np.int64)

print(solve(n, k, aaa, fff))
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
from functools import lru_cache

n = int(input())
lll = list(map(int, input().split()))
lll.sort()
ans = 0


@lru_cache()
def bisect_left_cache(x):
    return bisect_left(lll, x)


for i in range(n - 2):
    li = lll[i]
    for j in range(i + 1, n - 1):
        k = bisect_left_cache(li + lll[j])
        ans += k - j - 1
print(ans)


Fixed submission:
from bisect import bisect_left

n = int(input())
lll = list(map(int, input().split()))
lll.sort()
ans = 0

for i in range(n - 2):
    li = lll[i]
    for j in range(i + 1, n - 1):
        k = bisect_left(lll, li + lll[j], lo=j)
        ans += k - j - 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

n = int(input())
lll = list(map(int, input().split()))
lll.sort()
ans = 0

for i in range(n - 2):
    li = lll[i]
    for j in range(i + 1, n - 1):
        k = bisect_left(lll, li + lll[j], lo=j)
        ans += k - j - 1
print(ans)


Fixed submission:
from bisect import bisect_left

n = int(input())
lll = list(map(int, input().split()))
lll.sort()
ans = 0

for i in range(n - 2):
    li = lll[i]
    for j in range(i + 1, n - 1):
        k = bisect_left(lll, li + lll[j], lo=j)
        ans += k - j - 1
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
aaa = list(map(int, input().split()))
bbb = sorted(list(enumerate(aaa, start=1)), key=itemgetter(1))
print(*map(itemgetter(0), bbb))

Fixed submission:
from operator import itemgetter
n = int(input())
aaa = list(map(int, input().split()))
bbb = sorted(list(enumerate(aaa, start=1)), key=itemgetter(1))
print(*map(itemgetter(0), bbb))
Buggy python submission (verdict: Runtime Error):
from math import gcd
a, b = map(int, input().split())
g = gcd(a, b)
ans = 1
for i in range(2, int(g ** 0.5) + 1):
  if g % i != 0:
    continue
  while g % i == 0:
    g //= i
  ans += 1
print(ans)


Fixed submission:
from fractions import gcd
a, b = map(int, input().split())
g = gcd(a, b)
ans = 1
for i in range(2, int(g ** 0.5) + 1):
  if g % i != 0:
    continue
  while g % i == 0:
    g //= i
  ans += 1
if g > 1:
  ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

n, m = map(int, input().split())
INF = 10 ** 9
dp = [INF] * (1 << n)
dp[0] = 0
bits = [0] + [1 << i for i in range(n)]
get_bits = bits.__getitem__

for _ in [0] * m:
  a, b = map(int, sys.stdin.readline().split())
  s = sum(map(get_bits, map(int, sys.stdin.readline().split())))
  for t in range(1 << n):
    if (dp[t] == -1):
      continue
    dp[t | s] = min(dp[t | s], dp[t] + a)

print(dp[-1] if dp[-1] != INF else -1)


Fixed submission:
import sys

n, m = map(int, input().split())
INF = 10 ** 9
dp = [INF] * (1 << n)
dp[0] = 0
bits = [0] + [1 << i for i in range(n)]
get_bits = bits.__getitem__

for _ in [0] * m:
  a, b = map(int, sys.stdin.readline().split())
  s = sum(map(get_bits, map(int, sys.stdin.readline().split())))
  for t in range(1 << n):
    if (dp[t] == -1):
      continue
    dp[t | s] = min(dp[t | s], dp[t] + a)

print(dp[-1] if dp[-1] != INF else -1)

Buggy python submission (verdict: Runtime Error):
import sys

n, m = map(int, input().split())
dp = [-1] * (1 << n)
dp[0] = 0
bits = [0] + [1 << i for i in range(n)]
get_bits = bits.__getitem__

for _ in [0] * m:
  a, b = map(int, sys.stdin.readline())
  s = sum(map(get_bits, map(int, sys.stdin.readline())))
  for t in range(1 << n):
    if (dp[t] == -1):
      continue
    dp[t | s] = min(dp[t | s], dp[t] + a)

print(dp[-1])


Fixed submission:
import sys

n, m = map(int, input().split())
INF = 10 ** 9
dp = [INF] * (1 << n)
dp[0] = 0
bits = [0] + [1 << i for i in range(n)]
get_bits = bits.__getitem__

for _ in [0] * m:
  a, b = map(int, sys.stdin.readline().split())
  s = sum(map(get_bits, map(int, sys.stdin.readline().split())))
  for t in range(1 << n):
    if (dp[t] == -1):
      continue
    dp[t | s] = min(dp[t | s], dp[t] + a)

print(dp[-1] if dp[-1] != INF else -1)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heapreplace

n = int(input())
aaa = list(map(int, input().split()))
# print(*(f'{a:08b}' for a in aaa))

all_x = 0
for a in aaa:
    all_x ^= a
mask = ~all_x
bbb = [-(a & mask) for a in aaa if a & mask]
heapify(bbb)

ans = 0
while bbb and bbb[0] < 0:
    a = -heappop(bbb)
    l = a.bit_length()
    while bbb and (-bbb[0]).bit_length() == l:
        heapreplace(bbb, -(a ^ (-bbb[0])))
    b = 1 << (l - 1)
    if ans & b == 0:
        ans ^= a

print(2 * ans + all_x)


Fixed submission:
import numpy as np

n = int(input())
aaa = np.fromiter(map(int, input().split()), np.int64)

all_x = np.bitwise_xor.reduce(aaa)
mask = ~all_x
bbb = aaa & mask

ans = 0
while any(bbb):
    a = bbb.max()
    b = 1 << (int(a).bit_length() - 1)
    bbb[bbb & b > 0] ^= a
    if ans & b == 0:
        ans ^= a

print(2 * ans + all_x)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heapreplace

n = int(input())
aaa = list(map(int, input().split()))
# print(*(f'{a:08b}' for a in aaa))

all_x = 0
for a in aaa:
    all_x ^= a
mask = ~all_x
bbb = [-(a & mask) for a in aaa if a & mask]
heapify(bbb)

ans = 0
while bbb and bbb[0] < 0:
    a = -heappop(bbb)
    l = a.bit_length()
    while bbb and (-bbb[0]).bit_length() == l:
        x = a ^ (-bbb[0])
        if x:
            heapreplace(bbb, -x)
        else:
            heappop(bbb)
    b = 1 << (l - 1)
    if ans & b == 0:
        ans ^= a

print(2 * ans + all_x)


Fixed submission:
import numpy as np

n = int(input())
aaa = np.fromiter(map(int, input().split()), np.int64)

all_x = np.bitwise_xor.reduce(aaa)
mask = ~all_x
bbb = aaa & mask

ans = 0
while any(bbb):
    a = bbb.max()
    b = 1 << (int(a).bit_length() - 1)
    bbb[bbb & b > 0] ^= a
    if ans & b == 0:
        ans ^= a

print(2 * ans + all_x)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappop, heapreplace

n = int(input())
aaa = list(map(int, input().split()))
# print(*(f'{a:08b}' for a in aaa))

all_x = 0
for a in aaa:
    all_x ^= a
mask = ~all_x
bbb = [-(a & mask) for a in aaa]
heapify(bbb)

red = set()
while bbb and bbb[0] < 0:
    a = -heappop(bbb)
    l = a.bit_length()
    b = 1 << (l - 1)
    while bbb and (-bbb[0]).bit_length() == l:
        heapreplace(bbb, -(a ^ (-bbb[0])))
    red = {s ^ a if s & b else s for s in red}
    red.add(a)

ans = 0
for a in red:
    ans ^= a

print(2 * ans + all_x)


Fixed submission:
import numpy as np

n = int(input())
aaa = np.fromiter(map(int, input().split()), np.int64)

all_x = np.bitwise_xor.reduce(aaa)
mask = ~all_x
bbb = aaa & mask

ans = 0
while any(bbb):
    a = bbb.max()
    b = 1 << (int(a).bit_length() - 1)
    bbb[bbb & b > 0] ^= a
    if ans & b == 0:
        ans ^= a

print(2 * ans + all_x)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
from heapq import heappush, heappop


def solve(n, sss):
    keys = [-1] + sorted(sss.keys())
    m = keys.pop()
    if sss[m] != 1:
        return False
    k = keys[-1]
    q = [(-n, -m)]
    while k != -1:
        r, s = heappop(q)
        r = -r
        s = -s
        if r == 0:
            continue
        if k >= s:
            tmp = set()
            while q:
                tmp.add((-r, -s))
                r, s = heappop(q)
                r, s = -r, -s
                if k < s:
                    for item in tmp:
                        heappush(q, item)
                    break
            else:
                return False
        heappush(q, (-(r - 1), -k))
        heappush(q, (-(r - 1), -s))
        sss[k] -= 1
        if sss[k] == 0:
            keys.pop()
            k = keys[-1]
        # print(s, r, q, keys, sss)
    return True


n = int(input())
sss = Counter(map(int, input().split()))
print('Yes' if solve(n, sss) else 'No')


Fixed submission:
from collections import Counter
from heapq import heappop, heappush


def solve(n, sss):
    ccc = Counter(sss)
    keys = sorted(ccc.keys(), reverse=True)
    if ccc[keys[0]] != 1:
        return False

    q = [(1, keys[0])]
    for k in keys[1:]:
        nq = []
        for _ in range(ccc[k]):
            try:
                r, s = heappop(q)
            except IndexError:
                return False
            if r < n:
                nq.append((r + 1, k))
                heappush(q, (r + 1, s))
        for item in nq:
            heappush(q, item)

    return True


n = int(input())
sss = list(map(int, input().split()))
print('Yes' if solve(n, sss) else 'No')
Buggy python submission (verdict: Runtime Error):
from collections import Counter


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(n + 1)
single = 0
for a in reversed(aaa):
    single += bit.sum(a)
    bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
    ans = (ans + c * before * coef) % MOD
    before += c
print(ans)


Fixed submission:
from collections import Counter


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(2001)
single = 0
for a in reversed(aaa):
    single += bit.sum(a)
    bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2 % MOD
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
    ans = (ans + c * before * coef) % MOD
    before += c
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import Counter


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(n)
single = 0
for a in reversed(aaa):
    single += bit.sum(a - 1)
    bit.add(a, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
    ans = (ans + c * before * coef) % MOD
    before += c
print(ans)


Fixed submission:
from collections import Counter


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(2001)
single = 0
for a in reversed(aaa):
    single += bit.sum(a)
    bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2 % MOD
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
    ans = (ans + c * before * coef) % MOD
    before += c
print(ans)