import Control.Arrow
import Data.List
import qualified Data.ByteString.Char8 as B
import Data.Bits
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import Data.Foldable
import Control.Monad.ST

main :: IO ()
main = readLn >>= main'
    where
        main' n = breads >>= print . solve n 

solve :: Int -> [Int] -> Int 
solve n as = count True bs bs newVec 
    where
        bs = zip [1..] as

        newVec = V.fromList $ replicate 21 0

        count _ (x@(ix, vx) : xs) (y@(iy, vy) : ys) vs
            | isSatisfy ws = count True (x : xs) ys ws
            | otherwise = calc ix iy + count False xs (y : ys) us
            where
                us = V.modify (sub vx) vs
                ws = V.modify (add vy) vs
        count True ((ix, _) : _) _ _ = calc2 ix n
        count _ _ _ _ = 0

        isSatisfy = V.all (< 2)

        calc x y = y - x
        calc2 x y = (v * (v + 1)) `div` 2
            where
                v = y - x + 1

        diff f v vs = () <$ foldlM ff v [0..20]
                where
                    ff acc i
                        | acc .&. 1 == 1 = shiftR acc 1 <$ VM.modify vs f i
                        | otherwise = return $ shiftR acc 1
        
        sub :: Int -> VM.STVector s Int -> ST s ()
        sub = diff pred

        add :: Int -> VM.STVector s Int -> ST s ()
        add = diff succ 

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