-module(flags).
-export([flags/1]).

flags(A) ->
    Size = length(A),
    Arr = array:from_list(A),
    Peaks = compute_peaks(Arr, Size),
    Next = compute_next(Peaks, Size),
    max_flags(1, Size, Next, 0).

compute_peaks(_Arr, Size) when Size =< 1 ->
    array:new(max(Size, 1), {default, false});
compute_peaks(Arr, Size) ->
    Peaks0 = array:new(Size, {default, false}),
    lists:foldl(fun(I, Acc) ->
        Ai = array:get(I, Arr),
        Prev = array:get(I - 1, Arr),
        Next = case I + 1 < Size of
            true -> array:get(I + 1, Arr);
            false -> 0
        end,
        IsPeak = Prev < Ai andalso Ai > Next,
        array:set(I, IsPeak, Acc)
    end, Peaks0, lists:seq(1, Size - 1)).

compute_next(_Peaks, Size) when Size =:= 0 ->
    array:new(0);
compute_next(Peaks, Size) ->
    NextArr0 = array:set(Size - 1, -1, array:new(Size)),
    lists:foldl(fun(I, Acc) ->
        Val = case array:get(I, Peaks) of
            true -> I;
            false -> array:get(I + 1, Acc)
        end,
        array:set(I, Val, Acc)
    end, NextArr0, lists:seq(Size - 2, 0, -1)).

max_flags(I, Size, _Next, Result) when I * (I - 1) > Size ->
    Result;
max_flags(I, Size, Next, Result) ->
    Num = count_flags(0, 0, I, Size, Next),
    max_flags(I + 1, Size, Next, max(Result, Num)).

count_flags(Pos, Num, I, Size, _Next) when Pos >= Size orelse Num >= I ->
    Num;
count_flags(Pos, Num, I, Size, Next) ->
    case array:get(Pos, Next) of
        -1 -> Num;
        NextPos -> count_flags(NextPos + I, Num + 1, I, Size, Next)
    end.

func flags(a []int) int {
	size := len(a)

	peaks := make([]bool, size)
	for i := 1; i < size; i++ {
		nextVal := 0
		if i+1 < size {
			nextVal = a[i+1]
		}
		peaks[i] = a[i-1] < a[i] && a[i] > nextVal
	}

	next := make([]int, size)
	next[size-1] = -1
	for i := size - 2; i >= 0; i-- {
		if peaks[i] {
			next[i] = i
		} else {
			next[i] = next[i+1]
		}
	}

	result := 0
	for i := 1; i*(i-1) <= size; i++ {
		pos, num := 0, 0
		for pos < size && num < i {
			pos = next[pos]
			if pos == -1 {
				break
			}
			num++
			pos += i
		}
		if num > result {
			result = num
		}
	}

	return result
}

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

flags :: [Int] -> Int
flags a = result
  where
    n   = length a
    arr = listArray (0, n - 1) a :: Array Int Int
    at i
      | i >= 0 && i < n = arr ! i
      | otherwise       = 0

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

    nextArr :: Array Int Int
    nextArr = listArray (0, n - 1) [compute i | i <- [0 .. n - 1]]
      where
        compute i
          | i == n - 1 = if isPeak i then i else -1
          | isPeak i   = i
          | otherwise  = nextArr ! (i + 1)

    result = go 1 0
    go i best
      | i * (i - 1) > n = best
      | otherwise       = go (i + 1) (max best (countFlags i))

    countFlags i = walk 0 0
      where
        walk pos num
          | not (pos < n && num < i) = num
          | nextArr ! pos == -1      = num
          | otherwise                = walk (nextArr ! pos + i) (num + 1)

public class Solution {
    public static int flags(int[] a) {
        int size = a.length;
        boolean[] peaks = new boolean[size];

        for (int i = 1; i < size; i++) {
            int next = (i + 1 < size) ? a[i + 1] : 0;
            peaks[i] = a[i - 1] < a[i] && a[i] > next;
        }

        int[] next = new int[size];
        next[size - 1] = -1;
        for (int i = size - 2; i >= 0; i--) {
            next[i] = peaks[i] ? i : next[i + 1];
        }

        int i = 1;
        int result = 0;
        while (i * (i - 1) <= size) {
            int pos = 0;
            int num = 0;
            while (pos < size && num < i) {
                pos = next[pos];
                if (pos == -1) {
                    break;
                }
                ++num;
                pos += i;
            }
            i++;
            result = Math.max(result, num);
        }

        return result;
    }
}

(defun flags (a)
  (let* ((vec (coerce a 'vector))
         (size (length vec))
         (peaks (make-array size :initial-element nil))
         (next (make-array size :initial-element -1)))
    (loop for i from 1 below size
          do (setf (aref peaks i)
                   (and (< (aref vec (1- i)) (aref vec i))
                        (> (aref vec i) (if (< (1+ i) size) (aref vec (1+ i)) 0)))))
    (setf (aref next (1- size)) -1)
    (loop for i from (- size 2) downto 0
          do (setf (aref next i) (if (aref peaks i) i (aref next (1+ i)))))
    (let ((i 1) (result 0))
      (loop while (<= (* i (1- i)) size)
            do (let ((pos 0) (num 0))
                 (loop while (and (< pos size) (< num i))
                       do (progn
                            (setf pos (aref next pos))
                            (when (= pos -1) (return))
                            (incf num)
                            (incf pos i)))
                 (incf i)
                 (setf result (max result num))))
      result)))

function flags(array $a)
{

    $size  = count($a);
    $peaks = [false];
    $next  = [];
    for ($i = 1; $i < $size; $i++) {
        $peaks[$i] = $a[$i - 1] < $a[$i] && $a[$i] > ($a[$i + 1] ?? 0);
    }

    $next[$size - 1] = -1;
    for ($i = $size - 2; $i >= 0; $i--) {
        $next[$i] = $peaks[$i] ? $i : $next[$i + 1];
    }
    $i      = 1;
    $result = 0;
    while ($i * ($i - 1) <= $size) {
        $pos = 0;
        $num = 0;
        while ($pos < $size && $num < $i) {
            $pos = $next[$pos];
            if ($pos === -1) {
                break;
            }
            ++$num;
            $pos += $i;
        }
        $i++;
        $result = max($result, $num);
    }

    return $result;
}

def flags(a: list[int]) -> int:
    size = len(a)
    if size == 0:
        return 0

    peaks = [False] * size
    for i in range(1, size):
        next_val = a[i + 1] if i + 1 < size else 0
        peaks[i] = a[i - 1] < a[i] and a[i] > next_val

    next_peak = [0] * size
    next_peak[size - 1] = -1
    for i in range(size - 2, -1, -1):
        next_peak[i] = i if peaks[i] else next_peak[i + 1]

    i = 1
    result = 0
    while i * (i - 1) <= size:
        pos = 0
        num = 0
        while pos < size and num < i:
            pos = next_peak[pos]
            if pos == -1:
                break
            num += 1
            pos += i
        i += 1
        result = max(result, num)

    return result

fn flags(a: &[i64]) -> i64 {
    let size = a.len();
    let mut peaks = vec![false; size];
    for i in 1..size {
        let next = a.get(i + 1).copied().unwrap_or(0);
        peaks[i] = a[i - 1] < a[i] && a[i] > next;
    }

    let mut next_peak = vec![-1i64; size];
    if size > 0 {
        next_peak[size - 1] = -1;
        for i in (0..size - 1).rev() {
            next_peak[i] = if peaks[i] { i as i64 } else { next_peak[i + 1] };
        }
    }

    let mut i = 1i64;
    let mut result = 0i64;
    while i * (i - 1) <= size as i64 {
        let mut pos = 0i64;
        let mut num = 0i64;
        while pos < size as i64 && num < i {
            pos = next_peak[pos as usize];
            if pos == -1 {
                break;
            }
            num += 1;
            pos += i;
        }
        i += 1;
        result = result.max(num);
    }

    result
}

function flags(a: number[]): number {
  const size = a.length;
  const peaks: boolean[] = [false];
  const next: number[] = [];

  for (let i = 1; i < size; i++) {
    peaks[i] = a[i - 1] < a[i] && a[i] > (a[i + 1] ?? 0);
  }

  next[size - 1] = -1;
  for (let i = size - 2; i >= 0; i--) {
    next[i] = peaks[i] ? i : next[i + 1];
  }

  let i = 1;
  let result = 0;
  while (i * (i - 1) <= size) {
    let pos = 0;
    let num = 0;
    while (pos < size && num < i) {
      pos = next[pos];
      if (pos === -1) {
        break;
      }
      ++num;
      pos += i;
    }
    i++;
    result = Math.max(result, num);
  }

  return result;
}

frog_jmp() {
    local _x=$1 _y=$2 _d=$3
    echo $(( (_y - _x + _d - 1) / _d ))
}