import Data.Maybe
import qualified Data.ByteString.Char8 as B
import qualified Data.IntSet as IS
main=print.f.map(fst.fromJust.B.readInt).B.words=<<B.getContents
f(n:k:p)=n-k+1-g 0 0 n p-h 0 (IS.fromList a) b p where
  g i j v(w:p)=if v<w then g(i+1)(if (i+1)>=k then j+1 else j)w p else g 1 j w p
  g _ j _ _ = max 1 j-1
  (a,b)=splitAt k p
  h i s(w:p)(v:q)=h j t p q where
    j=if IS.findMin s==v && IS.findMax s<w then i+1 else i
    t=IS.insert w.IS.delete v$s
  h i _ _ _ = i