你是来自著名研究中心 Oskolkovo 的一名科学家。你发明了一种量子算法，可以使用 $\lceil \sqrt{n} \rceil$ 次量子操作对长度为 $n$ 的数组进行排序（不要问我们这是如何实现的）。你本想通过对一个包含 $n$ 个整数的数组进行排序来证明你发明的威力，但突然你发现来自 MIT 的竞争对手已经发表了一篇关于具有相同复杂度的类似算法的文章。因此，你决定稍微作弊一下，允许你的算法不仅可以对整个数组进行排序，还可以对某些子数组进行排序（如果这有助于减少量子操作的总次数）。这些操作是依次进行的，且在操作过程中被排序的子数组可以相交。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$) —— 数组中元素的个数。

下一行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 10^9$) —— 数组的元素。

输出格式

输出一行，表示对给定数组进行排序所需的最小量子操作次数。你可以通过对子数组进行排序来完成，已知对长度为 $l$ 的子数组进行排序的代价为 $\lceil \sqrt{l} \rceil$。

样例

输入样例 1

5
5 1 2 3 1

输出样例 1

3

输入样例 2

5
1 2 1 3 5

输出样例 2

2