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! |
