import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B
import qualified Data.IntMap.Strict as M

main :: IO ()
main = getLine >> readLine >>= print . solve 

solve :: [Int] -> Int
solve (x : xs) = count m x xs 
    where
        m = M.fromList . zip [1..x] $ repeat (0, 1)

count :: M.IntMap (Int, Int) -> Int -> [Int] -> Int
count m p (a : as) = count next a as 
    where
        d = a - p
        (pv, pb) = m M.! p
        (av, ab) = m M.! a
        limit = ab ^ a
        next
            | p < a = M.insert a (pv * (pb ^ d), pb) m
            | av + 1 < limit = M.insert a (av + 1, ab) m
            | otherwise = M.insert a (upbase ab a, ab + 1) m

count m p _ = snd $ m M.! p

upbase :: Int -> Int -> Int
upbase b n = loop b (b + 1) (n - 1)
    where
        loop acc v c
            | c > 0 = loop (acc + v * (b - 1)) (v * (b + 1)) $ c - 1
            | otherwise = acc  

readLine :: IO [Int]
readLine = unfoldr (\s -> second (maybe B.empty snd . B.uncons) <$> B.readInt s) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine