• + 0 comments

    Simple O(n lg n) solution in Haskell using Data.Set:

    import Control.Monad (replicateM_)
    import Data.Int
    import Data.Set hiding (foldl)
    import Data.List (sort)
    
    main :: IO ()
    main = getLine >> do
      l' <- getLine
      let l = preprocess $ fmap read $ words l'
      readLn >>= flip replicateM_
        (readLn >>= print . maybe (- 1) (flip findIndex l) . flip lookupGE l)
    
    preprocess :: [Int64] -> Set Int64
    preprocess = fromList . scanl (+) 0 . reverse . sort