import Data.List (elemIndex)
import Data.List.Split (splitOn)
import Data.Maybe (fromJust)
--import Control.Monad (liftM2)

incList :: Int -> Int -> Int -> [Int]
incList n q r = replicate r (q + 1) ++ replicate (n - r - 1) q

f :: [Int] -> [Int]
f xs = (drop (n - m) zs) ++ (take (n - m) zs)
  where p = maximum xs
        n = length xs
        q = p `div` n
        r = p `mod` n
        m = (fromJust $ elemIndex p xs) + 1
        ys = drop m (cycle xs)
        zs = (take (n - 1) $ zipWith (+) ys (incList n q r)) ++ [q]

g :: [[Int]] -> [[Int]]
g xs = (f $ head xs):xs

looped :: [Int] -> [[Int]]
looped xs = until (\ys -> (head ys) `elem` (tail ys)) g [xs]

solve1' :: [Int] -> Int
solve1' xs = (length $ looped xs) - 1

solve2' :: [Int] -> Int
solve2' xs = let (y:ys) = looped xs in (fromJust $ elemIndex y ys) + 1

parseInput :: [Char] -> [Int]
parseInput xs = map read $ splitOn " " xs

solve1 :: [Char] -> Int
solve1 = solve1' . parseInput

solve2 :: [Char] -> Int
solve2 = solve2' . parseInput

input :: [Char]
input = "4 10 4 1 8 4 9 14 5 1 14 15 0 15 3 5"