import Data.List import qualified Data.Set as S import qualified Data.Map as M main = do dat <- readFile "feel.in" mapM_ (pp.solve) $ parse dat parse str = f $ lines str where f (_:nums:rs) = map read (words nums) : f rs f _ = [] solve xs = f (S.fromList [-1,length xs]) ixs where ixs = sort $ zip xs [0..] sum = M.fromList $ zip [0..] (scanl (+) 0 xs) f _ [] = (-1,(0,0)) f s ((a,i):xs) = max (c,(l,u)) (f ns xs) where c = a * ((sum M.! u) - (sum M.! l)) (ls,us) = S.split i s (l ,u ) = (S.findMax ls + 1, S.findMin us) ns = S.insert i s pp (val,(l,u)) = do print val putStrLn $ show (l+1) ++ " " ++ show u