import Data.List
import qualified Data.ByteString.Char8 as B
import Data.Ord
import Control.Monad

main :: IO ()
main = breads >>= main'
    where
        main' [_, m] = replicateM m (build <$> breads) >>= print . solve . sortOn snd
        build [a, b] = (a, b)

solve :: [(Int, Int)] -> Int
solve = fst . foldl' ff (0, 0)
    where
        ff (acc, prev) (a, b)
            | prev < a = (acc + 1, b - 1)
            | otherwise = (acc, prev)

breads :: IO [Int]
breads = unfoldr uff <$> B.getLine
    where
        uff b = check <$> B.readInt b
        check (a, b)
            | B.null b = (a, b)
            | otherwise = (a, B.tail b)