实现了第一问，欢迎大佬们交流指导

module Main where

import Control.Monad.State
import Data.Array
import Data.List
import Data.Maybe

data Cache = Cache {carr :: Array Int Int, len :: Int}

updateCache :: Int -> State Cache ()
updateCache num = do
  Cache ca ca_len <- get
  if ca_len == 0
    then put $ Cache (ca // [(1, num)]) 1
    else updateCache' num

updateCache' :: Int -> State Cache ()
updateCache' num = do
  Cache ca ca_len <- get
  let idx_opt = fromMaybe (ca_len + 1) $ findFirstLess ca 1 ca_len num
  put $ Cache (ca // [(idx_opt, num)]) (max idx_opt ca_len)

main :: IO ()
main = do
  num_arr <- fmap read . words <$> getLine
  let cache_state = foldl1' (>>) (updateCache <$> num_arr)
      input_length = length num_arr
      zero_cache = (Cache (array (1, input_length) [(x, 0) | x <- [1 .. input_length]]) 0)
      ans = execState cache_state zero_cache
  putStrLn . show $ len ans

-- 在有序数组的指定范围 [start, end] 内，找到第一个小于 `target` 的元素的下标
-- 若不存在则返回 Nothing
findFirstLess :: (Ord a) => Array Int a -> Int -> Int -> a -> Maybe Int
findFirstLess arr start end target
  | start > end || outOfBounds start || outOfBounds end = Nothing
  | otherwise =
      let (lastCandidate, found) = binarySearch start end
       in if found then Just lastCandidate else Nothing
  where
    -- 检查索引是否越界
    (minIdx, maxIdx) = bounds arr
    outOfBounds idx = idx < minIdx || idx > maxIdx

    -- 二分查找核心逻辑
    binarySearch left right
      | left >= right = (right, isValid right)
      | otherwise =
          let mid = (left + right) `div` 2
              midVal = arr ! mid
           in if midVal <= target
                then binarySearch left mid -- 向左收缩范围
                else binarySearch (mid + 1) right -- 继续向右找更大的候选下标

    -- 检查最终下标是否有效
    isValid idx = idx >= start && idx <= end && arr ! idx < target