class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        def lis(nums):
            n = len(nums)
            memo = [-1] * n

            def dfs(i):
                if memo[i] != -1:
                    return memo[i]

                LIS = 1
                for j in range(i + 1, n):
                    if nums[i] < nums[j]:
                        LIS = max(LIS, 1 + dfs(j))

                memo[i] = LIS
                return LIS

            return max(dfs(i) for i in range(n))

        return lis([e[1] for e in envelopes])

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        def lis(nums):
            LIS = [1] * n

            for i in range(n - 1, -1, -1):
                for j in range(i + 1, n):
                    if nums[i] < nums[j]:
                        LIS[i] = max(LIS[i], 1 + LIS[j])
            return max(LIS)

        return lis([e[1] for e in envelopes])

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        def lis(nums):
            dp = []
            dp.append(nums[0])

            LIS = 1
            for i in range(1, len(nums)):
                if dp[-1] < nums[i]:
                    dp.append(nums[i])
                    LIS += 1
                    continue

                idx = bisect_left(dp, nums[i])
                dp[idx] = nums[i]

            return LIS

        return lis([e[1] for e in envelopes])

class SegmentTree:
    def __init__(self, N):
        self.n = N
        while (self.n & (self.n - 1)) != 0:
            self.n += 1
        self.tree = [0] * (2 * self.n)

    def update(self, i, val):
        self.tree[self.n + i] = val
        j = (self.n + i) >> 1
        while j >= 1:
            self.tree[j] = max(self.tree[j << 1], self.tree[j << 1 | 1])
            j >>= 1

    def query(self, l, r):
        if l > r:
            return 0
        res = float('-inf')
        l += self.n
        r += self.n + 1
        while l < r:
            if l & 1:
                res = max(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, self.tree[r])
            l >>= 1
            r >>= 1
        return res

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        def lis(nums):
            def compress(arr):
                sortedArr = sorted(set(arr))
                order = []
                for num in arr:
                    order.append(bisect_left(sortedArr, num))
                return order

            nums = compress(nums)
            n = len(nums)
            segTree = SegmentTree(n)

            LIS = 0
            for num in nums:
                curLIS = segTree.query(0, num - 1) + 1
                segTree.update(num, curLIS)
                LIS = max(LIS, curLIS)
            return LIS

        return lis([e[1] for e in envelopes])