Using running stack, precompute the $$$\text{pr1}[]$$$ and $$$\text{nx1}[]$$$ to store the previous/next $$$j$$$ such that $$$A_j \lt A_i$$$.

Also precompute $$$\text{pr2}[]$$$ and $$$\text{nx2}[]$$$ for $$$A_j \gt A_i$$$

Bruteforce the index of the $$$\max A_i$$$.

For each max $$$A_i$$$, there are $$$\mathcal{O}(\sqrt[3]{A_i})$$$ divisors, so we can bruteforce the divisors that will be $$$\min A_j$$$.

For current $$$A_i$$$, and current divisor $$$X$$$, find the largest $$$j$$$ such that $$$j\leq i$$$ and $$$A_j = X$$$.

Also find the smallest $$$k$$$ such that $$$i\leq k$$$ and $$$A_k = X$$$.

If $$$j$$$ doesn't exist, or $$$j \leq \text{pr2}_i$$$, set $$$j$$$ to $$$i$$$

If $$$k$$$ doesn't exist, or $$$\text{nx2}_i \leq k$$$ set $$$k$$$ to $$$i$$$

$$$j = \max(\text{pr2}_i+1, \text{pr1}_j+1), k = \min(\text{nx2}_i-1, \text{nx1}_k-1)$$$

$$$\text{ans} = \max(\text{ans}, k-j+1)$$$

Let $$$C$$$ = $$$\max_{i=1,\dots,n} A_i$$$

Time complexity: $$$O(N\sqrt[3]{C}+C\log{C})$$$

UPD: Made some minor corrections + Code in comments below

use std::io::{Read, Write};

fn solve(cin: &mut impl Iterator<Item = usize>, cout: &mut impl Write) -> Option<()> {
    let n = cin.next()?;
    let aa = Vec::from_iter((0..n).filter_map(|_| cin.next()));

    let mut maxints = vec![vec![]; 1 << 17];
    let mut minints = vec![vec![]; 1 << 17];

    let mut mxq = vec![];
    let mut mnq = vec![];
    for i in 0..=n {
        let a = aa.get(i).cloned().unwrap_or(1 << 17);
        let mut l = i;
        while !mxq.is_empty() && mxq.last() < Some(&(a, 0)) {
            let (b, j) = mxq.pop()?;
            maxints[b].push((j, i));
            l = j;
        }
        if mxq.is_empty() || mxq.last() > Some(&(a, i)) {
            mxq.push((a, l));
        }

        let a = aa.get(i).cloned().unwrap_or(0);
        let mut l = i;
        while !mnq.is_empty() && mnq.last() > Some(&(a, i)) {
            let (b, j) = mnq.pop()?;
            minints[b].push((j, i));
            l = j;
        }
        if mnq.is_empty() || mnq.last() < Some(&(a, 0)) {
            mnq.push((a, l));
        }
    }

    type STT = (usize, usize);
    let mut st = vec![vec![STT::default(); aa.len()]; aa.len().ilog2() as usize + 1];
    for i in 0..st[0].len() {
        st[0][i] = (aa[i], aa[i]);
    }
    fn op(a: STT, b: STT) -> STT {
        (a.0.min(b.0), a.1.max(b.1))
    }
    for l in 1..st.len() {
        for i in 0..st[l].len() {
            let j = (i + (1 << l >> 1)).min(st[l].len() - 1);
            st[l][i] = op(st[l - 1][i], st[l - 1][j]);
        }
    }
    let rq = |r: std::ops::Range<usize>| {
        let l2 = r.len().ilog2() as usize;
        op(st[l2][r.start], st[l2][r.end - (1 << l2)])
    };

    let mut ans = 1;
    for mn in 2..1 << 17 {
        for mx in (mn..1 << 17).step_by(mn) {
            // if !minints[mn].is_empty() && !maxints[mx].is_empty() {
            //     println!("\n? {mn} {:?} x {mx} {:?}", minints[mn], maxints[mx]);
            // }
            for &(lmin, rmin) in &minints[mn] {
                let j = maxints[mx].partition_point(|s| s.1 <= lmin);
                for &(lmax, rmax) in &maxints[mx][j..] {
                    if lmax >= rmin {
                        break;
                    }
                    let (mn, mx) = rq(lmin.max(lmax)..rmin.min(rmax));
                    // println!(
                    //     "\t{mn} ({lmin}..{rmin}) x {mx} ({lmax}..{rmax}) = {}",
                    //     rmin.min(rmax) - lmin.max(lmax)
                    // );
                    if mx % mn == 0 {
                        ans = ans.max(rmin.min(rmax) - lmin.max(lmax));
                    }
                }
            }
        }
    }

    writeln!(cout, "{}", ans).ok()
}

fn main() {
    let mut cout = std::io::BufWriter::new(std::io::stdout());
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut cin = s.split_ascii_whitespace().filter_map(|x| x.parse().ok());
    while let Some(_) = solve(&mut cin, &mut cout) {}
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::{rng, Rng};
    use std::time::Instant;

    fn gen(n: usize) -> Vec<usize> {
        let aa = Vec::from_iter(std::iter::repeat_with(|| rng().random_range(2..1000)).take(n));
        let mut input = vec![];
        input.extend([n]);
        input.extend(aa);
        input
    }

    fn solve_slow(cin: &mut impl Iterator<Item = usize>, cout: &mut impl Write) -> Option<()> {
        let n = cin.next()?;
        let aa = Vec::from_iter((0..n).filter_map(|_| cin.next()));

        type STT = (usize, usize);
        let mut st = vec![vec![STT::default(); aa.len()]; aa.len().ilog2() as usize + 1];
        for i in 0..st[0].len() {
            st[0][i] = (aa[i], aa[i]);
        }
        fn op(a: STT, b: STT) -> STT {
            (a.0.min(b.0), a.1.max(b.1))
        }
        for l in 1..st.len() {
            for i in 0..st[l].len() {
                let j = (i + (1 << l >> 1)).min(st[l].len() - 1);
                st[l][i] = op(st[l - 1][i], st[l - 1][j]);
            }
        }
        let rq = |r: std::ops::Range<usize>| {
            let l2 = r.len().ilog2() as usize;
            op(st[l2][r.start], st[l2][r.end - (1 << l2)])
        };

        let mut ans = 1;
        for i in 1..=n {
            for j in 0..i {
                let (mn, mx) = rq(j..i);
                if mx % mn == 0 {
                    ans = ans.max(i - j);
                }
            }
        }

        writeln!(cout, "{}", ans).ok()
    }

    #[test]
    fn test_valid() {
        for _ in 0..10 {
            let input = gen(rng().random_range(5..10));
            let mut outs = vec![];
            let mut outf = vec![];
            solve_slow(&mut input.iter().cloned(), &mut outs);
            solve(&mut input.iter().cloned(), &mut outf);
            let outs = String::from_utf8(outs).unwrap();
            let outf = String::from_utf8(outf).unwrap();
            assert_eq!(outs, outf, "DIFF\n{input:?}\nslow\n{}fast\n{}", outs, outf);
        }
    }

    #[test]
    fn bench() {
        for n in [3, 4, 5, 6] {
            let input = gen(10usize.pow(n));
            let start = Instant::now();
            let mut outs = vec![];
            solve(&mut input.into_iter(), &mut outs);
            let dt = Instant::now().duration_since(start);
            println!("10^{n} = {dt:?} {}", outs.len());
        }
    }
}