import Control.Monad
import Control.Monad.ST
import qualified Data.ByteString.Char8 as C
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM

main = C.interact $ put . sol . get

get = U.unfoldr (C.readInt . C.dropWhile (<'0'))

put = C.unlines . fmap (C.pack . show) . U.toList

sol v = runST $ do
  h <- UM.replicate (10^5+1) 0
  U.forM_ as $ UM.unsafeModify h (+ 1)
  r <- UM.unsafeNew q
  let
    f s i bc = do
      let (b,c) = (bc U.! 0,bc U.! 1)
      cnt <- UM.unsafeRead h b
      UM.unsafeWrite h b 0
      UM.unsafeModify h (+ cnt) c
      UM.unsafeWrite r i (s+cnt*(c-b))
      return $ s+cnt*(c-b)
  V.ifoldM_ f (U.sum as) qs
  U.unsafeFreeze r
  where
  n = v U.! 0
  as = U.slice 1 n v
  q = v U.! (n+1)
  qs = V.unfoldrN q (Just . U.splitAt 2) $ U.unsafeDrop (n+2) v