import qualified Data.ByteString.Char8 as C
import Data.List

main = C.interact $ C.pack . show . sol . get

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

sol (n:a:b:a':b':xs) = f [min a a',max a a'] [min b b',max b b'] xs
  where
  f sa sb [] = 1+if odd n then sb!!1-sa!!1 else sum sb-sum sa
  f sa sb (a:b:xs) = f (g sa a) (g sb b) xs

g [l,h] x 
  | x < l     = [x,l,h]
  | h < x     = [l,h,x]
  | otherwise = [l,x,h]

g [l,m,h] x 
  | x < m     = [max x l,m]
  | otherwise = [m,min x h]