Codeforces/1899/B.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.StringTokenizer;

class Solution {
    void solve() {
        var n = fs.nextInt();
        var a = fs.readArray(n);

        var prefix = new long[n + 2];
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + a[i];
        }

        long max = 0;
        for (int k = 1; n / k > 1; ++k) {
            if (n % k != 0) {
                continue;
            }

            long _min = Long.MAX_VALUE, _max = Long.MIN_VALUE;
            for (int i = 0, count = n / k; i < count; ++i) {
                long truck = prefix[(i + 1) * k] - prefix[i * k];

                if (truck < _min) {
                    _min = truck;
                }
                if (truck > _max) {
                    _max = truck;
                }
            }

            if (_max - _min > max) {
                max = _max - _min;
            }
        }

        answer(max);
    }

    // region runner
    private static final boolean SINGLE = false;
    void run() {
        if (SINGLE) {
            solve();
        } else {
            int N = fs.nextInt();
            for (int i = 0; i < N; ++i) {
                solve();
            }
        }

        out.close();
    }

    public static void main(String[] args) {
        new Solution().run();
    }
    // endregion runner

    // region math
    static final Random random = new Random();
    static final int mod = 1_000_000_007;

    static long add(long a, long b) {
        return (a + b) % mod;
    }

    static long sub(long a, long b) {
        return ((a - b) % mod + mod) % mod;
    }

    static long mul(long a, long b) {
        return (a * b) % mod;
    }

    static long exp(long base, long exp) {
        if (exp == 0)
            return 1;
        long half = exp(base, exp / 2);
        if (exp % 2 == 0)
            return mul(half, half);
        return mul(half, mul(half, base));
    }

    static long[] factorials = new long[2_000_001];
    static long[] invFactorials = new long[2_000_001];

    static void precompFacts() {
        factorials[0] = invFactorials[0] = 1;
        for (int i = 1; i < factorials.length; i++)
            factorials[i] = mul(factorials[i - 1], i);
        invFactorials[factorials.length - 1] = exp(factorials[factorials.length - 1], mod - 2);
        for (int i = invFactorials.length - 2; i >= 0; i--)
            invFactorials[i] = mul(invFactorials[i + 1], i + 1);
    }

    static long nCk(int n, int k) {
        return mul(factorials[n], mul(invFactorials[k], invFactorials[n - k]));
    }
    // endregion math

    // region sorts
    static void ruffleSort(int[] a) {
        int n = a.length;// shuffle, then sort
        for (int i = 0; i < n; i++) {
            int oi = random.nextInt(n), temp = a[oi];
            a[oi] = a[i];
            a[i] = temp;
        }
        Arrays.sort(a);
    }

    static void sort(int[] a) {
        ArrayList<Integer> l = new ArrayList<>();
        for (int i : a)
            l.add(i);
        Collections.sort(l);
        for (int i = 0; i < a.length; i++)
            a[i] = l.get(i);
    }
    // endregion sorts

    // region output
    private PrintWriter out = new PrintWriter(System.out);

    private void yes() {
        out.println("YES");
    }

    private void no() {
        out.println("NO");
    }

    private void yesno(boolean ans) {
        out.println(ans ? "YES" : "NO");
    }

    private void answer(boolean ans) {
        yesno(ans);
    }

    private <T> void answer(T ans) {
        out.println(ans);
    }
    // endregion output

    // region input
    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
    private FastScanner fs = new FastScanner();
    // endregion input

}