{-# LANGUAGE BangPatterns #-} import Control.Monad.State import Data.Bits import Data.Bool import Data.Char import Data.Coerce import Data.Word import qualified Data.ByteString as BS import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Vector.Fusion.Stream.Monadic as VFSM import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM type Parser a = StateT BSC8.ByteString Maybe a runParser :: Parser a -> BSC8.ByteString -> Maybe (a, BSC8.ByteString) runParser = runStateT {-# INLINE runParser #-} int :: Parser Int int = coerce $ BSC8.readInt . BSC8.dropWhile isSpace {-# INLINE int #-} seqInput :: Int -> IO (VU.Vector Int) seqInput n = VU.unfoldrN n (runParser int) <$> BSC8.getLine stream :: Monad m => Int -> Int -> VFSM.Stream m Int stream !l !r = VFSM.Stream step l where step x | x < r = return $ VFSM.Yield x (x + 1) | otherwise = return $ VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] stream #-} rep :: Monad m => Int -> (Int -> m ()) -> m () rep n = flip VFSM.mapM_ (stream 0 n) {-# INLINE rep #-} streamR :: Monad m => Int -> Int -> VFSM.Stream m Int streamR !l !r = VFSM.Stream step (r - 1) where step x | x >= l = return $ VFSM.Yield x (x - 1) | otherwise = return $ VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] streamR #-} rev :: Monad m => Int -> Int -> (Int -> m ()) -> m () rev l r = flip VFSM.mapM_ (streamR l (r + 1)) {-# INLINE rev #-} main :: IO () main = do n <- readLn :: IO Int w <- seqInput n let s = VU.sum w if odd s then putStrLn "impossible" else do dp <- VUM.replicate (5001) True rep n $ \i -> rev (s `div` 2) (w VU.! i) $ \j -> do dpjwi <- VUM.unsafeRead dp (j - w VU.! i) VUM.unsafeModify dp (\k -> k .|. dpjwi) j putStrLn . bool "impossible" "possible" =<< VUM.unsafeRead dp (s `div` 2)