Migrated from Lutece 3114 Mon panache!Ⅰ

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：ST表

顺便说一下，他最后想带走的东西。Mon panache...就是羽饰。

是的，他帽子上的羽饰。

那好像可以引申为“男子汉的勇气”呢。

在夺走一切的死神面前，西哈诺最后留下的话语很精彩啊。

特别是死时对着天空喊出Mon panache!...真让人陶醉。

对这种勇气无动于衷的人……对这种行为莫名惊诧的人……

如果那种家伙是正常的话，那我觉得我还是奇怪点好。

螺旋马太的仪式即将开始，作为救世主大人的忠实信徒——橘希实香，肩负着准备仪式的重任。

仪式的准备过程可以抽象为如下的问题，给定一个长度为 $n$ 的非负整数序列 $a_1,a_2,\cdots,a_n$ ，记作 $A$ 。

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

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

现在小橘子想要知道，有多少个 $k$ 满足 $1\le k\le n$ ，且对于任意 $1\le i<j\le n$ 有 $A'_{k,i}\le A'_{k,j}$ 。

Input

输入的第一行包括一个正整数 $n$ ，表示非负整数序列的长度。

第二行包括 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$ ，表示给定的序列 $A$ 。

Output

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

Samples

13
1 1 4 5 1 4 1 9 1 9 8 1 0

1

4
114 514 1919 810

2

Constraints

$1\le n\le 10^6,0\le a_i\le 10^9$

Resources

2024 UESTC ICPC Training for Data Structures