Shifting
Statement
Peanut is sensing some interference in his electronic equipments! He used a sensor and recorded the readings 1ms apart.
You decided to help him find out what is causing those signals. First step is to find the strongest frequency in the reading, so if its 50-60
Hz we know it is because of the power lines.
Input
First line contain 1 integer, N
Second line contains N integers of the reading, taken 1ms apart
Output
The strongest frequency, if there is more than 1, pick the lowest one. The base reading is not counted. (Eg 1 1 1 1 1 1 1)
Sample
Input:
8
1 -1 1 -1 1 -1 1 -1
Output:
500
The sequence does a full oscillation every 2ms, so its 500Hz
Scoring
Subtask 1 (4%): N <= 8
Subtask 2 (20%): N <= 100
Subtask 3 (66%): N <= 1000
Subtask 4 (10%): N <= 1000000
Disclaimer
The author, JieFeng has not provided a solution that can fully solve ANY of the subtasks within the time limit. It is advised not to attempt this question. My condolences to you for wasting time reading this problem statement.
Limits:
-1000000000 <= Ai <= 1000000000 (10^9)