G. Jump Sort
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

塑料从 u2x1 那拿到了一个长度为 $$$n$$$ 的排列$$$\dag$$$，打算给它排个序，使得这个排列变为升序。

塑料有一种神奇的魔法。在排序前，他将选择一个 $$$x$$$ ($$$1 \leq x \leq n$$$)，接下来，他将进行以下操作任意次（当然可以是 $$$0$$$，如果本身已经有序）：

  • 选择距离为 $$$x$$$ 的两个下标 $$$i$$$ 和 $$$j$$$（即满足$$$|i - j| = x$$$），并交换 $$$a_i$$$ 和 $$$a_j$$$。

在排序开始前，他想知道有多少个 $$$x$$$ 可以帮助他使得排列最终有序，但是笨笨塑料并不知道怎么做，所以请你帮帮他吧！

$$$\dag$$$ 在这里，我们定义一个长度为 $$$n$$$ 的排列为一个包含从 $$$1$$$ 到 $$$n$$$ 这 $$$n$$$ 个不同的整数的序列，且每个整数恰好出现一次。

Input

第一行输入一个正整数 $$$n$$$ ($$$1 \leq n \leq 5 \times 10^5$$$)，表示序列长度；

第二行输入一个长度为 $$$n$$$ 的排列 $$$a_1,a_2,...,a_n$$$ ($$$1 \leq a_i \leq n$$$)。

Output

输出一个正整数 $$$ans$$$，即有多少个 $$$x$$$ 可以帮助塑料完成排序。

Example
Input
4
3 2 1 4
Output
2
Note

样例解释：

  • $$$x = 1$$$ 时，一种可能的排序过程如下：
  • $$$3 ~ 2 ~ 1 ~ 4 \to 3 ~ 1 ~ 2 ~ 4 \to 1 ~ 3 ~ 2 ~ 4 \to 1 ~ 2 ~ 3 ~ 4$$$
  • $$$x = 2$$$ 时，塑料可以将 $$$1$$$ 和 $$$3$$$ 互换完成排序。
  • $$$x = 3,4$$$ 时，可以证明不存在可行的排序方法。

所以答案为 $$$2$$$。