The first thing we should do is remove duplicates of $a_i$. After this, we'll assume all the $a_i$ are distinct, and let $N'$ denote the number of distinct $a_i$. Note that if $N' \leq 3$, then any $L$ satisfies the second condition. So, the answer is just $1 + 2 + \cdots + (\min a_i)/4$.

Subtask 1 ($a_i\leq 10^6$):

For this subtask, we first consider the following naive algorithm: Let $U = (\min a_i)/4$ be an upper bound on $L$. For each $1\leq L \leq U$, we can check how many possible values of $a_i\pmod L$ there are. It turns out that if we break once we see 4 distinct values, then we will pass this subtask.

Here is an implementation:

N = input()
S = list(set([int(x) for x in input().split()]))

U = min(S) // 4
if len(S) < 4:
    print(U*(U+1)//2)
    exit()

def test(L):
    mods = set()
    for a in S:
        mods.add(a%L)
        if len(mods) >= 4:
            return False
    return True

print(sum([L for L in range(1, U+1) if test(L)]))

Now, why do we pass? A naive analysis says that this time should take $O(UN')$ time, where $U\leq 2.5\cdot 10^5$ and $N' \leq 10^4$. So this should not actually be fast enough.

Let's consider the test function again, which takes $O(N')$ time in the worst case. However, note that in order for the function to not return after 4 iterations (and so only take $O(1)$ time), among $a_1\bmod L, a_2\bmod L, a_3\bmod L, a_4\bmod L$, there are at most $3$ distinct values.

This implies that $L$ divides one of $(a_2 - a_1, a_3 - a_1, a_4 - a_1, a_3 - a_2, a_4 - a_2, a_4 - a_3)$. Now, if we let $n(A)$ denote the maximum number of divisors that a number at most $A$ can have, then we see that for all but at most $6n(10^6)$ values of $L$, we break after 4 loop iterations. So, we can bound the runtime of this step by $O(U + n(10^6)\cdot N')$, where we run the loop $O(U)$ times, and only run past 4 iterations $O(n(10^6))$ times. Since $n(10^6) \leq 2\cdot 10^3$ (here, note that any positive integer $x$ has at most $2\sqrt x$ divisors), this will run in time.

General Case ($a_i \leq 4\cdot 10^9$):

Now, $U$ can be up to $10^9$, so the preceding algorithm is too slow. On the other hand, $n(4\cdot 10^9)$ is actually $2000$, so we just need to speed up the $O(U)$ step. To do this, instead of checking every possible value of $L$ and seeing if it breaks after trying the first four $a_i$, we will instead explicitly only consider $L$ that would not have broken. The only such values of $L$ are those that divide one of $(a_2 - a_1, a_3 - a_1, a_4 - a_1, a_3 - a_2, a_4 - a_2, a_4 - a_3)$. So, we can just compute these divisors. We can compute the divisors of $A$ in $O(\sqrt A)$ time, so the total runtime of this is $O(\sqrt{\max a_i} + n(4\cdot 10^9) \cdot N')$, which runs in time.

Here is an implementation:

N = input()
S = list(set([int(x) for x in input().split()]))

U = min(S) // 4
if len(S) < 4:
    print(U*(U+1)//2)
    exit()

divs = set()
for i, s in enumerate(S[:4]):
    for _, r in enumerate(S[i:4]):
        diff = abs(s-r)
        for t in range(1, int(diff**(0.5) + 1)):
            if diff%t == 0:
                divs.add(t)
                divs.add(diff//t)

def test(L):
    if L > U:
        return False
    mods = set()
    for a in S:
        mods.add(a%L)
        if len(mods) >= 4:
            return False
    return True

print(sum([L for L in divs if test(L)]))

Danny Mittal's implementation:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Cowlendar {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        Set<Long> months = new HashSet<>();
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        long maxWeekLength = Integer.MAX_VALUE;
        for (; n > 0; n--) {
            long month = Long.parseLong(tokenizer.nextToken());
            months.add(month);
            maxWeekLength = Math.min(maxWeekLength, month / 4L);
        }
        if (months.size() <= 3) {
            System.out.println((maxWeekLength * (maxWeekLength + 1L)) / 2L);
        } else {
            Set<Long> candidates = new HashSet<>();
            Long[] distinctMonths = months.toArray(new Long[0]);
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < j; k++) {
                    long diff = Math.abs(distinctMonths[k] - distinctMonths[j]);
                    for (long x = 1; x <= 100000; x++) {
                        if (diff % x == 0L) {
                            candidates.add(x);
                            candidates.add(diff / x);
                        }
                    }
                }
            }
 
            long answer = 0;
            for (long candidate : candidates) {
                if (candidate <= maxWeekLength) {
                    Set<Long> seen = new HashSet<>();
                    for (long month : distinctMonths) {
                        seen.add(month % candidate);
                    }
                    if (seen.size() <= 3) {
                        answer += candidate;
                    }
                }
            }
            System.out.println(answer);
        }
    }
}