#!/usr/bin/env stack
-- stack --resolver=lts-9.12 --install-ghc runghc
{-
Cannibal numbers
=======================
 
- https://r...content-available-to-author-only...d.it/76qk58
 
Sorts the input and makes the largest numbers eat the smallest, one at a time.
 
Maintains a list of "cannibalised" numbers (and their cannibals)
in case a switch needs to be made
(i.e. for a 3 to eat a 2 instead of a 1, such to make room for another 2 to eat a 1).
 
Unfortunately it's quite inefficient due to the recurring `sortBy s` of that list,
which could have been improved by using some kind of cursor.
-}
module Main
  ( main
  , cannibalise
  ) where
 
import           Data.List
import           Data.Ord
 
cannibalise :: ([Int], [Int]) -> [Int]
cannibalise (ns, qs) = map (recurse sns 0 []) qs
  where
    sns = sortBy (comparing Down) ns
 
recurse :: [Int] -> Int -> [(Int, Int)] -> Int -> Int
recurse ns c us q =
  case ns of
    (f:l)
      | f >= q -> recurse l (c + 1) us q
      | ll < 1 -> c
      | f > last l -> recurse ((f + 1) : init l) c ((f, last l) : us) q
      | otherwise ->
        case sortBy s us of
          ((fus, sus):tus)
            | f < fus && f > sus ->
              recurse ((f + 1) : init l) c ((fus, f) : (f, sus) : tus) q
            | otherwise -> c
          _ -> c
      where ll = length l
            s (fx, sx) (fy, sy)
              | sx == sy = compare fy fx
              | otherwise = compare sx sy
    _ -> c
 
main = interact io
  where
    io i =
      case lines i of
        (_:ns:qs:_) ->
          show $ cannibalise (map read (words ns), map read (words qs))

IyEvdXNyL2Jpbi9lbnYgc3RhY2sKLS0gc3RhY2sgLS1yZXNvbHZlcj1sdHMtOS4xMiAtLWluc3RhbGwtZ2hjIHJ1bmdoYwp7LQpDYW5uaWJhbCBudW1iZXJzCj09PT09PT09PT09PT09PT09PT09PT09CgotIGh0dHBzOi8vci4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uZC5pdC83NnFrNTgKClNvcnRzIHRoZSBpbnB1dCBhbmQgbWFrZXMgdGhlIGxhcmdlc3QgbnVtYmVycyBlYXQgdGhlIHNtYWxsZXN0LCBvbmUgYXQgYSB0aW1lLgoKTWFpbnRhaW5zIGEgbGlzdCBvZiAiY2FubmliYWxpc2VkIiBudW1iZXJzIChhbmQgdGhlaXIgY2FubmliYWxzKQppbiBjYXNlIGEgc3dpdGNoIG5lZWRzIHRvIGJlIG1hZGUKKGkuZS4gZm9yIGEgMyB0byBlYXQgYSAyIGluc3RlYWQgb2YgYSAxLCBzdWNoIHRvIG1ha2Ugcm9vbSBmb3IgYW5vdGhlciAyIHRvIGVhdCBhIDEpLgoKVW5mb3J0dW5hdGVseSBpdCdzIHF1aXRlIGluZWZmaWNpZW50IGR1ZSB0byB0aGUgcmVjdXJyaW5nIGBzb3J0Qnkgc2Agb2YgdGhhdCBsaXN0LAp3aGljaCBjb3VsZCBoYXZlIGJlZW4gaW1wcm92ZWQgYnkgdXNpbmcgc29tZSBraW5kIG9mIGN1cnNvci4KLX0KbW9kdWxlIE1haW4KICAoIG1haW4KICAsIGNhbm5pYmFsaXNlCiAgKSB3aGVyZQoKaW1wb3J0ICAgICAgICAgICBEYXRhLkxpc3QKaW1wb3J0ICAgICAgICAgICBEYXRhLk9yZAoKY2FubmliYWxpc2UgOjogKFtJbnRdLCBbSW50XSkgLT4gW0ludF0KY2FubmliYWxpc2UgKG5zLCBxcykgPSBtYXAgKHJlY3Vyc2Ugc25zIDAgW10pIHFzCiAgd2hlcmUKICAgIHNucyA9IHNvcnRCeSAoY29tcGFyaW5nIERvd24pIG5zCgpyZWN1cnNlIDo6IFtJbnRdIC0+IEludCAtPiBbKEludCwgSW50KV0gLT4gSW50IC0+IEludApyZWN1cnNlIG5zIGMgdXMgcSA9CiAgY2FzZSBucyBvZgogICAgKGY6bCkKICAgICAgfCBmID49IHEgLT4gcmVjdXJzZSBsIChjICsgMSkgdXMgcQogICAgICB8IGxsIDwgMSAtPiBjCiAgICAgIHwgZiA+IGxhc3QgbCAtPiByZWN1cnNlICgoZiArIDEpIDogaW5pdCBsKSBjICgoZiwgbGFzdCBsKSA6IHVzKSBxCiAgICAgIHwgb3RoZXJ3aXNlIC0+CiAgICAgICAgY2FzZSBzb3J0QnkgcyB1cyBvZgogICAgICAgICAgKChmdXMsIHN1cyk6dHVzKQogICAgICAgICAgICB8IGYgPCBmdXMgJiYgZiA+IHN1cyAtPgogICAgICAgICAgICAgIHJlY3Vyc2UgKChmICsgMSkgOiBpbml0IGwpIGMgKChmdXMsIGYpIDogKGYsIHN1cykgOiB0dXMpIHEKICAgICAgICAgICAgfCBvdGhlcndpc2UgLT4gYwogICAgICAgICAgXyAtPiBjCiAgICAgIHdoZXJlIGxsID0gbGVuZ3RoIGwKICAgICAgICAgICAgcyAoZngsIHN4KSAoZnksIHN5KQogICAgICAgICAgICAgIHwgc3ggPT0gc3kgPSBjb21wYXJlIGZ5IGZ4CiAgICAgICAgICAgICAgfCBvdGhlcndpc2UgPSBjb21wYXJlIHN4IHN5CiAgICBfIC0+IGMKCm1haW4gPSBpbnRlcmFjdCBpbwogIHdoZXJlCiAgICBpbyBpID0KICAgICAgY2FzZSBsaW5lcyBpIG9mCiAgICAgICAgKF86bnM6cXM6XykgLT4KICAgICAgICAgIHNob3cgJCBjYW5uaWJhbGlzZSAobWFwIHJlYWQgKHdvcmRzIG5zKSwgbWFwIHJlYWQgKHdvcmRzIHFzKSk=

OSAxCjIgMiAyIDIgMiAyIDEgMSAxCjQ=

9 1
2 2 2 2 2 2 1 1 1
4