Hide

Problem M
Successful Zoom

Your boss likes to see numbers going up as proof that your company is successful. To help with this, you came up with the idea to summarize a list of numbers by “zooming out,” that is, to discard everything except every $k^{th}$ number in the list, for some $k\ge 1$.

Business has been tough lately, with lots of ups and downs. However, if you pick the right value of $k$, maybe you can prove to your boss that things aren’t so bad after all! If possible, you should find the smallest value of $k$ such that $x_ k<x_{2k}<\dots <x_{qk}$, where $q=\lfloor \frac nk\rfloor $, and the list $x_ k,x_{2k},\dots ,x_{qk}$ contains at least two elements.

Input

The first line contains an integer $n$, with $2\le n\le 10^5$. The second line contains $n$ integers $x_1,x_2,\dots ,x_ n$ describing the list of numbers. It is guaranteed that $0\le x_ i\le 2^{30}$ for $i=1,\dots ,n$.

Output

If possible, display the smallest value $k\ge 1$ for which $x_ k,x_{2k},\dots ,x_{qk}$ (where $q=\lfloor \frac nk\rfloor $) is strictly increasing and has at least two elements. If no such value of $k$ exists, display the word “ABORT!

Sample Input 1 Sample Output 1
10
1 2 3 4 5 6 7 8 9 10
1
Sample Input 2 Sample Output 2
8
1 8 2 7 3 6 4 5
3
Sample Input 3 Sample Output 3
10
9 8 8 4 4 3 10 1 1 0
ABORT!

Please log in to submit a solution to this problem

Log in