import Data.Array (Array, listArray, (!))

peaks :: [Int] -> Int
peaks a
  | n <= 2          = 0
  | totalPeaks == 0 = 0
  | otherwise       = result
  where
    n   = length a
    arr = listArray (0, n - 1) a :: Array Int Int

    isPeakAt i = i > 0 && i + 1 < n && arr ! i > arr ! (i - 1) && arr ! i > arr ! (i + 1)

    -- running count of peaks seen in a[0 .. i], for i in [0 .. n-2]
    sumList    = scanl (\acc i -> acc + (if isPeakAt i then 1 else 0)) 0 [1 .. n - 2]
    sumArr     = listArray (0, n - 2) sumList :: Array Int Int
    totalPeaks = sumArr ! (n - 2)

    -- sum[n-1] mirrors sum[n-2] in the original algorithm
    sumAt idx
      | idx == n - 1 = totalPeaks
      | otherwise    = sumArr ! idx

    peakPositions = [i | i <- [1 .. n - 2], isPeakAt i]
    lastPeak      = last peakPositions
    dist          = max (gapMax (-1) peakPositions) (n - lastPeak)
      where
        gapMax _    []       = 0
        gapMax prev (p : ps) = max (p - prev) (gapMax p ps)

    -- can every block of size i (n/i blocks) contain at least one peak?
    checkGroups i = walk 0 i
      where
        walk lastSum j
          | j > n                     = True
          | sumAt (j - 1) <= lastSum  = False
          | otherwise                 = walk (sumAt (j - 1)) (j + i)

    candidates = [i | i <- [(dist `div` 2) + 1 .. dist - 1], n `mod` i == 0, checkGroups i]

    result = case candidates of
      (i : _) -> n `div` i
      []      -> n `div` head [l | l <- [dist ..], n `mod` l == 0]