Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())

if H == 1 or W == 1:
    print(1)
else:
    if (H * W) % 2 == 1:
        ans = H * W // 2 + 1
    else:
        ans = H * W // 2
print(ans)


Fixed submission:
H, W = map(int, input().split())

if H == 1 or W == 1:
    print(1)
else:
    if (H * W) % 2 == 1:
        ans = H * W // 2 + 1
    else:
        ans = H * W // 2
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())
Q = int(input())

flag = 0
for _ in range(Q):
    q = input()
    if q == "1":
        flag += 1
    else:
        _, t, c = q.split()
        if flag % 2 == 0:
            if t == "1":
                S.insert(0, c)
            else:
                S.append(c)
        else:
            if t == "2":
                S.insert(0, c)
            else:
                S.append(c)

if flag % 2 == 1:
    S.reverse()
print("".join(S))


Fixed submission:
from collections import deque

S = list(input())
d = deque(S)
Q = int(input())

flag = 0
for _ in range(Q):
    q = input()
    if q == "1":
        flag += 1
    else:
        _, t, c = q.split()
        if flag % 2 == 0:
            if t == "1":
                d.appendleft(c)
            else:
                d.append(c)
        else:
            if t == "2":
                d.appendleft(c)
            else:
                d.append(c)

if flag % 2 == 1:
    d.reverse()
print("".join(list(d)))

Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())
Q = int(input())

for _ in range(Q):
    q = input()
    if q == "1":
        S.reverse()
    else:
        _, t, c = q.split()
        if t == "1":
            S.insert(0, c)
        else:
            S.append(c)

print("".join(S))


Fixed submission:
from collections import deque

S = list(input())
d = deque(S)
Q = int(input())

flag = 0
for _ in range(Q):
    q = input()
    if q == "1":
        flag += 1
    else:
        _, t, c = q.split()
        if flag % 2 == 0:
            if t == "1":
                d.appendleft(c)
            else:
                d.append(c)
        else:
            if t == "2":
                d.appendleft(c)
            else:
                d.append(c)

if flag % 2 == 1:
    d.reverse()
print("".join(list(d)))
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N, P = map(int, input().split())
    S = input()

    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
    else:
        val = [0] * P
        val[0] += 1
        for i in range(N):
            cur = int(S[N - i - 1 :]) % P
            val[cur] += 1

        ans = 0
        for v in val:
            ans += v * (v - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N, P = map(int, input().split())
    S = input()

    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
    else:
        val = [0] * P
        cur = 0
        tenfactor = 1
        val[cur] += 1
        for i in range(N):
            cur = (cur + int(S[N - i - 1]) * tenfactor) % P
            tenfactor *= 10
            tenfactor %= P
            val[cur] += 1

        ans = 0
        for v in val:
            ans += v * (v - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N, P = map(int, input().split())
    S = input()

    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
    else:
        val = [0] * P
        val[0] += 1
        for i in range(N):
            cur = int(S[N - i - 1 :]) % P
            val[cur] += 1

        ans = 0
        for v in val:
            ans += v * (v - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N, P = map(int, input().split())
    S = input()

    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i + 1
    else:
        val = [0] * P
        cur = 0
        tenfactor = 1
        val[cur] += 1
        for i in range(N):
            cur = (cur + int(S[N - i - 1]) * tenfactor) % P
            tenfactor *= 10
            tenfactor %= P
            val[cur] += 1

        ans = 0
        for v in val:
            ans += v * (v - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
P = list(map(int, input().split()))

M = [sum(P[i:i+K]) / 2 + K/2 for i in range(N-K+1)]

print(max(M))


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

M = [sum(P[:K]) / 2 + K / 2]

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


print(max(M))

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
P = list(map(int, input().split()))

E = [(p+1)/2 for p in P]
M = [sum(E[i:i+K]) for i in range(N-K+1)]
print(max(M))


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

M = [sum(P[:K]) / 2 + K / 2]

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


print(max(M))

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
P = list(map(int, input().split()))

E = [(p+1)/2 for p in P]

M = 0
for i in range(0, N-K+1):
    exp = sum(E[i:i+K])
    if M < exp:
        M = exp

print(M)


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

M = [sum(P[:K]) / 2 + K / 2]

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


print(max(M))
Buggy python submission (verdict: Runtime Error):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = input()
    length = len(N)
    K = int(input())

    # 左からi桁目まで見て，N以下が確定していて，0でない数字がk個ある数字の個数
    dp_1 = [[0] * (10) for _ in range(length)]

    # 左からi桁目まで見て，N以下が確定していなくて，0でない数字がk個ある数字の個数
    dp_2 = [[0] * (10) for _ in range(length)]

    dp_1[0][0] = 1
    dp_1[0][1] = int(N[0]) - 1

    dp_2[0][1] = 1

    for i in range(1, length):
        # 小さいのが確定しているものに対して，0以外のものを追加
        for k in range(1, K + 2):
            dp_1[i][k] += dp_1[i - 1][k - 1] * 9

        # 小さいものが確定しているものに対して，0を追加
        for k in range(0, K + 2):
            dp_1[i][k] += dp_1[i - 1][k]

        # 大小がわからないものから，小さいのが確定する
        if N[i] == "0":
            for i in range(K + 2):
                dp_2[i][k] += dp_2[i - 1][k]
        else:
            # 0を追加する
            for k in range(K + 2):
                dp_1[i][k] += dp_2[i - 1][k]

            # その他の数字を追加
            for k in range(1, K + 2):
                dp_1[i][k] += dp_2[i - 1][k - 1] * (int(N[i]) - 1)

            # 依然として大小関係がわからない
            for k in range(1, K + 2):
                dp_2[i][k] += dp_2[i - 1][k - 1]

    ans = dp_1[-1][K] + dp_2[-1][K]
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = input()
    length = len(N)
    K = int(input())

    # 左からi桁目まで見て，N以下が確定していて，0でない数字がk個ある数字の個数
    dp_1 = [[0] * (10) for _ in range(length)]

    # 左からi桁目まで見て，N以下が確定していなくて，0でない数字がk個ある数字の個数
    dp_2 = [[0] * (10) for _ in range(length)]

    dp_1[0][0] = 1
    dp_1[0][1] = int(N[0]) - 1

    dp_2[0][1] = 1

    for i in range(1, length):
        # 小さいのが確定しているものに対して，0以外のものを追加
        for k in range(1, K + 2):
            dp_1[i][k] += dp_1[i - 1][k - 1] * 9

        # 小さいものが確定しているものに対して，0を追加
        for k in range(0, K + 2):
            dp_1[i][k] += dp_1[i - 1][k]

        # 大小がわからないものから，小さいのが確定する
        if N[i] == "0":
            for k in range(K + 2):
                dp_2[i][k] += dp_2[i - 1][k]
        else:
            # 0を追加する
            for k in range(K + 2):
                dp_1[i][k] += dp_2[i - 1][k]

            # その他の数字を追加
            for k in range(1, K + 2):
                dp_1[i][k] += dp_2[i - 1][k - 1] * (int(N[i]) - 1)

            # 依然として大小関係がわからない
            for k in range(1, K + 2):
                dp_2[i][k] += dp_2[i - 1][k - 1]

    ans = dp_1[-1][K] + dp_2[-1][K]
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    H, N = map(int, input().split())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    dp = [float("inf")] * (H + 1)
    dp[0] = 0

    for h in range(0, H):
        for a, b in zip(A, B):
            tmp = dp[h] + b
            if h + a >= H and tmp < dp[H]:
                dp[H] = tmp
            elif h + a < H and tmp < dp[h + a]:
                dp[h + a] = tmp

    print(dp[-1])


if __name__ == "__main__":
    main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    H, N = map(int, input().split())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    dp = [float("inf")] * (H + 1)
    dp[0] = 0

    for h in range(0, H):
        for a, b in zip(A, B):
            tmp = dp[h] + b
            if h + a >= H and tmp < dp[H]:
                dp[H] = tmp
            elif h + a < H and tmp < dp[h + a]:
                dp[h + a] = tmp

    print(dp[-1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [float("inf")] * (H + 1)
dp[0] = 0

for h in range(0, H):
    for a, b in zip(A, B):
        tmp = dp[h] + b
        if h + a >= H and tmp < dp[H]:
            dp[H] = tmp
        elif h + a < H and tmp < dp[h + a]:
            dp[h + a] = tmp

print(dp[-1])


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    H, N = map(int, input().split())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    dp = [float("inf")] * (H + 1)
    dp[0] = 0

    for h in range(0, H):
        for a, b in zip(A, B):
            tmp = dp[h] + b
            if h + a >= H and tmp < dp[H]:
                dp[H] = tmp
            elif h + a < H and tmp < dp[h + a]:
                dp[h + a] = tmp

    print(dp[-1])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
correct = []
missed = [0 for _ in range(N)]
penalty = 0

for _ in range(M):
    p, s = input().split()
    p = int(p)

    if s == "AC" and p not in correct:
        correct.append(p)
        penalty += missed[p - 1]
    elif s == "WA" and p not in correct:
        missed[p - 1] += 1

print(len(correct), penalty)


Fixed submission:
N, M = map(int, input().split())
correct = [0 for _ in range(N)]
missed = [0 for _ in range(N)]
penalty = 0
ans = 0
for _ in range(M):
    p, s = input().split()
    p = int(p)

    if s == "AC" and correct[p - 1] == 0:
        correct[p - 1] = 1
        penalty += missed[p - 1]
    elif s == "WA" and correct[p - 1] == 0:
        missed[p - 1] += 1

print(sum(correct), penalty)
Buggy python submission (verdict: Runtime Error):
from collections import deque

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

H += 2
W += 2

grid = "#" * W
for _ in range(H - 2):
    grid += "#" + input().split()
grid += "#" * W


def bfs(start):
    INF = 10 * 9
    dist = [INF] * (H * W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1, 1, W, -W):
            # next place
            w = v + move
            # wall or not
            if grid[w] == "#":
                continue

            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)

    return max(x for x in dist if x < INF)


answer = max(bfs(v) for v in range(H * W) if grid[v] != "#")
print(answer)


Fixed submission:
from collections import deque

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

H += 2
W += 2

grid = "#" * W
for _ in range(H - 2):
    grid += "#" + input() + "#"
grid += "#" * W


def bfs(start):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1, 1, W, -W):
            # next place
            w = v + move
            # wall or not
            if grid[w] == "#":
                continue

            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)

    return max(x for x in dist if x < INF)


answer = max(bfs(v) for v in range(H * W) if grid[v] != "#")
print(answer)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()

ans = 0
i = 0
while i < N:
    if S[i] == "A":
        i += 1
        if S[i] == "B":
            i += 1
            if S[i] == "C":
                ans += 1
            else:
                i += 1
        else:
            i += 1
    else:
        i += 1

print(ans)


Fixed submission:
N = int(input())
S = input()

ans = 0
for i in range(N):
    if S[i : i + 3] == "ABC":
        ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = []

for _ in range(N):
    a = int(input())
    xy = []
    for _ in range(a):
        x, y = map(int, input().split())
        xy.append((x, y))
    A.append(xy)

ans = 0
cnt = 0
bit = format(cnt, "#015b")
for _ in range(2 ** N):
    d = {}
    for i in range(N):
        d[i] = int(bit[-i])

    flag = False
    for i in range(N):
        for x, y in A[i]:
            if d[i] == 1:
                if d[x - 1] == y:
                    pass
                else:
                    flag = True
                    break
            else:
                if d[x - 1] == y:
                    flag = True
                    break
                else:
                    pass

        if flag:
            break

    if flag:
        cnt += 1
        bit = format(cnt, "#015b")
        continue

    a = sum(list(map(int, list(bit[2:]))))
    ans = max(a, ans)
    cnt += 1
    bit = format(cnt, "#015b")


print(ans)


Fixed submission:
def is_nth_bit_set(x, n):
    if x & (1 << n):
        return 1
    else:
        return 0


N = int(input())
comment = {}
for i in range(N):
    A = int(input())
    comment[i] = []
    for _ in range(A):
        x, y = map(int, input().split())
        x -= 1
        comment[i].append((x, y))

ans = 0
for i in range(2 ** N):
    judge = [None] * N
    flag = True
    for j in range(N):
        honest = is_nth_bit_set(i, j)
        judge[j] = honest

    for j in range(N):
        honest = judge[j]
        if not honest:
            continue
        for x, y in comment[j]:
            if honest:
                if judge[x] == y:
                    continue
                else:
                    flag = False
                    break
    if not flag:
        continue

    tmp = sum(judge)
    if tmp > ans:
        ans = tmp
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    ans = 1
    cnt = [0, 0, 0]
    for a in A:
        i = cnt.index(a)
        c = cnt.count(a)
        cnt[i] += 1
        ans *= c
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    ans = 1
    cnt = [0, 0, 0]
    for a in A:
        if a not in cnt:
            print(0)
            return
        i = cnt.index(a)
        c = cnt.count(a)
        cnt[i] += 1
        ans *= c
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def factorization(N):
    d = {}
    for n in range(2, N + 1):
        tmp = n
        for i in range(2, int(n ** 0.5) + 1):
            if tmp % i == 0:
                cnt = 0
                while tmp % i == 0:
                    cnt += 1
                    tmp //= i
                if i not in d:
                    d[i] = cnt
                else:
                    d[i] += cnt

        if tmp != 1:
            if tmp not in d:
                d[tmp] = 1
            else:
                d[tmp] += 1

    return d


def main():
    N = int(input())
    d = factorization(N)
    d = [v for k, v in d.items() if v > 1]
    cnt = {2: 0, 4: 0, 14: 0, 24: 0, 74: 0}
    cnt[2] = len(d)
    for i in range(len(d)):
        val = d[i]
        if val >= 74:
            cnt[74] += 1
        if val >= 24:
            cnt[24] += 1
        if val >= 14:
            cnt[14] += 1
        if val >= 4:
            cnt[4] += 1

    ans = cnt[74]
    ans += cnt[24] * (cnt[2] - 1)
    ans += cnt[14] * (cnt[4] - 1)
    ans += cnt[4] * (cnt[4] - 1) // 2 * (cnt[2] - 2)

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
import heapq

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N, M = map(int, input().split())
    d = {i: [] for i in range(M + 1)}
    for _ in range(N):
        a, b = map(int, input().split())
        if a > M:
            continue
        d[a].append(b)

    ans = 0
    q = []
    heapq.heapify(q)
    for i in range(M, 0, -1):
        a = M - i + 1
        for b in d[a]:
            heapq.heappush(q, -b)
        if q:
            b = heapq.heappop(q)
            ans += -b

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def bellman_ford(edges, n_nodes, start, goal):
    dist = [float("inf") for _ in range(n_nodes)]
    dist[start] = 0

    for i in range(2 * n_nodes):
        for fro, to, cost in edges:
            if dist[to] > dist[fro] + cost:
                dist[to] = dist[fro] + cost
                if i == n_nodes - 1:
                    dist[to] = -float("inf")

    return -dist[goal]


def main():
    N, M, P = map(int, input().split())
    edges = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        edges.append((a - 1, b - 1, -c + P))

    ans = bellman_ford(edges, N, 0, N - 1)
    if ans == float("inf"):
        print(-1)
    else:
        print(max(ans, 0))


if __name__ == "__main__":
    main()


Fixed submission:
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def bellman_ford(edges, n_nodes, start, goal):
    dist = [float("inf") for _ in range(n_nodes)]
    dist[start] = 0

    for i in range(2 * n_nodes):
        for fro, to, cost in edges:
            if dist[to] > dist[fro] + cost:
                dist[to] = dist[fro] + cost
                if i == n_nodes - 1:
                    dist[to] = -float("inf")

    return -dist[goal]


def main():
    N, M, P = map(int, input().split())
    edges = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        edges.append((a - 1, b - 1, -c + P))

    ans = bellman_ford(edges, N, 0, N - 1)
    if ans == float("inf"):
        print(-1)
    else:
        print(max(ans, 0))


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color = [A[0]]

    for i in range(1, N):
        idx = bisect_left(color, A[i])
        if idx == 0:
            color = [A[i]] + color
        else:
            color[idx - 1] = A[i]

    print(len(color))


if __name__ == "__main__":
    main()


Fixed submission:
import sys
from bisect import bisect_left
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color = deque([A[0]])

    for i in range(1, N):
        idx = bisect_left(color, A[i])
        if idx == 0:
            color.appendleft(A[i])
        else:
            color[idx - 1] = A[i]

    print(len(color))


if __name__ == "__main__":
    main()

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

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color = [A[0]]

    for i in range(1, N):
        idx = bisect_left(color, A[i])
        if idx == 0:
            color = [A[i]] + color
        else:
            color[idx - 1] = A[i]

    print(len(color))


if __name__ == "__main__":
    main()


Fixed submission:
import sys
from bisect import bisect_left
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color = deque([A[0]])

    for i in range(1, N):
        idx = bisect_left(color, A[i])
        if idx == 0:
            color.appendleft(A[i])
        else:
            color[idx - 1] = A[i]

    print(len(color))


if __name__ == "__main__":
    main()