Jump Sort
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

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


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


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


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


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

输入描述:

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

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

输出描述:

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

输入

复制 
4
3 2 1 4

输出

复制 
2

备注:

样例解释：

  • 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。