Оптимизация алгоритма "Забавная игра"

Помогите, пожалуйста, оптимизировать алгоритм по времени выполнения. Признаюсь, переписал его с питона, потому что мой выполнялся ещё дольше. Мне кажется нужно концептуально поменять решение. Вот задание:

Забавная игра

Вы с друзьями играете в следующую игру. Друзья пишут на доске подряд N натуральных чисел. Ваша задача — найти как можно больше подряд идущих чисел, которые бы делились на одно и то же число, большее 1. Так как вручную искать ответ сложно, вы решили написать программу, которая сделает работу за вас.

Входные данные

В первой строке входных данных задано число N(1 ≤ N ≤ 100000). Во второй строке записано через пробел N целых чисел A1...AN(1 ≤ Ai ≤ 1000, 1 ≤ i ≤ N). Это те самые числа, которые написали ваши друзья. Они даны в том же порядке, в котором они расположены на доске.

Выходные данные

Ваша программа должна вывести одно целое число — наибольшее количество подряд идущих чисел заданной последовательности, которые бы делились на одно и то же натуральное число, большее 1.

Пример: Ввод 3 6 10 15 Вывод 2

Моя программа:

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <deque>
#include <iterator>

using namespace std;

using lli = long long;
using lld = long double;
using ulli = unsigned long long;
using usi = unsigned short;

template <typename T2>
T2 gcd(T2 a, T2 b)
{
    if (a < b) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    lli n, mx = 0, cur_g;
    cin >> n;
    vector <lli> a;
    lli x;
    for (lli i = 0; i < n; i++) {
        cin >> x;
        a.push_back(x);
    }

    for (lli i = 0; i < n; i++) {
        cur_g = a[i];
        if (n - i < mx) break;
        lli p = 0;
        for (lli j = i; j < n; j++) {
            cur_g = gcd(cur_g, a[j]);
            if (cur_g == 1) break;
            ++p;
            if (mx < p) mx = p;
        }
    }
    cout << mx;
}