from bisect import bisect_left
from typing import List
from typing import Tuple


def lis(seq: List) -> Tuple[List[int], List[int]]:
    """Get LIS (Longest Increasing Subsequence).
    Args:
        seq: List of numbers.
    Returns:
        Size of LIS, LIS
    Landau notation: O(nlogn).
    See:
    https://qiita.com/python_walker/items/d1e2be789f6e7a0851e5
    https://atcoder.jp/contests/typical90/submissions/23271010
    """


    sub_seq = [seq[0]]
    sub_seq_size = list()

    for i in range(len(seq)):
        if seq[i] > sub_seq[-1]:
            sub_seq.append(seq[i])
        else:
            index = bisect_left(sub_seq, seq[i])
            sub_seq[index] = seq[i]
        
        sub_seq_size.append(len(sub_seq))
        
    return sub_seq_size, sub_seq