Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:1024 MB

#870. 山脉

附加文件 统计

对于序列 $a_1 , a_2 , \dots , a_n$ ,若它的子段 $a_l , a_{l + 1} , \dots , a_r$ , 如果存在 $mid \in [l + 1, r - 1]$ ,使得 $a_l , a_{l + 1} , \dots , a_{mid}$ 是不减的, $a_{mid} , a_{mid + 1} , \dots , a_r$ 是不增的,且 $r - l + 1 \geq 3$ , 就称这个子段是山型的。

若对于整数 $k$ $(3 \leq k \leq n)$ , 若子段 $[1 , k]$ , $[k + 1 , 2k]$ , $ \dots $ , $[(m - 1)k + 1,mk]$ , $[mk + 1 , n]$ 都是山型的,且 $mk \leq n , n - mk < k$ , 我们就称序列 $a$ 是一个山脉。

现在给定一个正整数序列 $a$ , 其中值为 $-1$ 的数可以表示任何数,请你找出所有使得该序列为山脉的整数 $k$ 。

输入格式

第一行输入一个整数 $ n $ , 表示序列的长度 $ ( 1 \leq n \leq 10^5 ) $。

第二行输入 $ n $ 个整数 $ a_1 , a_2 , a_3 , \dots , a_n $ 表示给定的序列 。 $ ( 1 \leq a_i \leq 10^9 \ 或 \ a_i = -1 )$

输出格式

第一行一个整数 $m$ , 表示满足要求的 $k$ 的数量。

接下来 $m$ 行,每行一个整数,从小到大输出所有满足要求的 $k$ 。

样例输入

11
7 -1 11 10 -1 -1 26 14 9 12 -1

样例输出

1
4