module Main where

import Data.Word
import Data.Bits
import System.Environment

data Tree = Both Tree Tree | Leaf Word64 deriving Show

-- Atomic Swap
swap' :: Word64 -> Tree -> Tree -> Tree
swap' 0 a b = Both a b
swap' 1 a b = Both b a

-- Swaps distant values in parallel; corresponds to a Red Box
warp' :: Word64 -> Tree -> Tree -> Tree
warp' s (Leaf a)   (Leaf b)   = swap' (xor (if a > b then 1 else 0) s) (Leaf a) (Leaf b)
warp' s (Both a b) (Both c d) = join' (warp' s a c) (warp' s b d)

-- Rebuilds the warped tree in the original order
join' :: Tree -> Tree -> Tree
join' (Both a b) (Both c d) = Both (Both a c) (Both b d)

-- Recursively warps each sub-tree; corresponds to a Blue/Green Box
flow' :: Word64 -> Tree -> Tree
flow' s (Leaf a)   = Leaf a
flow' s (Both a b) = down' s (warp' s a b)

-- Propagates Flow downwards
down' :: Word64 -> Tree -> Tree
down' s (Leaf a)   = Leaf a
down' s (Both a b) = Both (flow' s a) (flow' s b)

-- Bitonic Sort
sort' :: Word64 -> Tree -> Tree
sort' s (Leaf a)   = Leaf a
sort' s (Both a b) = flow' s (Both (sort' 0 a) (sort' 1 b))

-- Generates a tree of depth `n`
gen' :: Word64 -> Word64 -> Tree
gen' 0 x = Leaf x
gen' n x = Both (gen' (n - 1) (x * 2)) (gen' (n - 1) (x * 2 + 1))

-- Reverses a tree
rev' :: Tree -> Tree
rev' (Leaf a)   = Leaf a
rev' (Both a b) = Both (rev' b) (rev' a)

-- Sums a tree
sum' :: Tree -> Word64
sum' (Leaf a)   = a
sum' (Both a b) = sum' a + sum' b

main :: IO ()
main = do
  n <- read . head <$> getArgs :: IO Word64
  print $ sum' (sort' 0 (rev' (gen' n 0)))