main :: IO ()
main = do
    _ <- getLine 
    xs <- map (read :: String -> Int) . words <$> getLine
    q <- readLn
    -- let xs' = [(head ys, length ys) | ys <- group xs]
    -- analyze q xs'
    let xs' = [count x xs | x <- [1..10^5]]
        curSum = sum xs
    analyze q curSum xs'
        where
            count n [] = n
            count n (x:xs)
                | n == x = count (n + 1) xs
                | otherwise = count n xs
            analyze n cur xs = do
                [b, c] <- map (read :: String -> Int) . words <$> getLine
                let bCount = xs !! (b - 1)
                    cCount = xs !! (c - 1)
                    res = cur + ((c - b) * bCount)
                    replaced = rep b c cCount xs
                putStrLn $ show res
                if n == 1
                    then return ()
                    else analyze (n - 1) res replaced
            rep _ _ _ [] = []
            rep bIdx cIdx cPls (x:xs)
                | bIdx == 0 = 0 : rep (-1) (cIdx - 1) cPls xs
                | cIdx == 0 = (x + cPls) : rep (bIdx - 1) (-1) 0 xs
                | otherwise  = x : rep (bIdx - 1) (cIdx - 1) cPls xs