题目描述

给定一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$，记作 $A$。

对于正整数 $k$，按照以下方式得到序列 $A'_k$：

• 将 $A$ 划分为 $\left\lceil \dfrac{n}{k} \right\rceil$ 段，第 $i$ 段为 $a_{k(i-1)+1}, a_{k(i-1)+2}, \dots, a_{\min\{ki, n\}}$；
• 每一段升序排序后依次连接得到 $A'_k$。

试求有多少个 $k$ 满足 $1 \le k \le n$，且对于任意 $1 \le i < j \le n$ 有 $A'_{k,i} \le A'_{k,j}$。

输入格式

• 第一行包含一个正整数 $n$（$1 \le n \le 10^6$），表示非负整数序列 $A$ 的长度。
• 第二行包含 $n$ 个非负整数 $a_1, \dots, a_n$（$0 \le a_i \le 10^9$），表示给定的序列 $A$。

输出格式

一行包含一个整数，表示答案。

Samples

4
114 514 1919 810

2

Limitation

1s, 1024KiB for each test case.