Stone Skipping (SUJEBI)

Interview

Time limit2sMemory limit512 MB

Summary

For each step size d, sum the cells at multiples of d and pick the d with the largest sum, printing 0 0 if that sum is not positive.

Level: Medium5 of 10
Topics: Math, Brute force, Prefix sum, Implementation
Solved: No attempts yet

Problem

A sharp change in the climate let invasive species spread through many rivers of Daegwak. The government discussed the problem and settled on the Flat Dumpling Plan: skip a stone across a river and wipe out the invasive species in the cells the stone touches.

The river picked for the plan has width $L$ , and the river is modeled as $L$ consecutive cells numbered 1 through $L$ . The environment ministry scored every cell by how dangerous the species living there is. Some cells hold native species, so a score can be negative.

Throwing two or more stones makes your arm hurt, so exactly one stone is thrown. Depending on the power of the throw, the stone bounces at a fixed interval $d$ ( $1 \le d \le L$ ), passing over cell $d$ , then cell $2d$ , and so on up to cell $\lfloor L/d \rfloor d$ . Find the natural number $d$ that maximizes the sum of the scores of the cells the stone passes over.

Input

The first line contains the river width $L$ . $L$ is an integer between 1 and 1,000,000.

The second line contains the scores of the $L$ cells in order starting from cell 1, separated by spaces. Every score is an integer between -50,000 and 50,000.

Output

Print the $d$ that maximizes the sum of the scores and that maximum sum, separated by a space. If several values of $d$ reach the maximum, print the smallest one. If the maximum sum is 0 or less, running the plan is not worth it, so print 0 0.

Examples3

Example 1
Input
```
6
2 -5 4 -4 6 2
```
Expected output
```
3 6
```
Example 2
Input
```
1
5
```
Expected output
```
1 5
```
Example 3
Input
```
5
-1 -2 -3 -4 -5
```
Expected output
```
0 0
```