In this HackerRank The Strange Function problem you need to complete the function maximumValue which takes an integer array as input and returns the maximum value of f among all subsegments [l,r].

HackerRank The Strange Function problem solution


Problem solution in Python programming.

from math import gcd

def parseInput(f):
    return [f(x) for x in input().split()]

n=int(input())
array=parseInput(int)
stack=[]
answer=float('-inf')
for number in array:
    for i in range(len(stack)):
        stack[i][0]=gcd(abs(stack[i][0]),abs(number))
        stack[i][1]+=number
        if number > stack[i][2]:
            stack[i][1]-=number-stack[i][2]
            stack[i][2]=number

    stack.append([number,0,number])
    newStack=[]
    for i in range(len(stack)):
        if newStack and newStack[-1][0] == stack[i][0]:
            if newStack[-1][1] <= stack[i][1]:
                if newStack[-1][1]+newStack[-1][2] > stack[i][1]+stack[i][2]:
                    newStack.append(stack[i])
                    continue
                newStack[-1][1]=stack[i][1]
                newStack[-1][2]=stack[i][2]
        else:
            newStack.append(stack[i])
    stack = newStack[:]
    answer=max(answer,max(abs(stack[i][0])*stack[i][1] for i in range(len(stack))))
print(answer)


Problem solution in Java Programming.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
import java.util.TreeMap;

public class Solution98 {
    static final Scanner scanner = new Scanner(System.in);
    static class Segment {
        int left, right, val;
        Segment(int left, int right, int val) {
            this.left = left;
            this.right = right;
            this.val = val;
        }
    }
    private static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        }
        return gcd(y, x % y);
    }

    public static void main(String[] args) {
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        long ans = 0;
        long sum = 0;
        TreeMap<Integer, Integer> tmap = new TreeMap<>();
        SegmentTree tree = new SegmentTree(n);
        Deque<Segment> dq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            TreeMap<Integer, Integer> segmentTree = new TreeMap<>();
            for (int j : tmap.keySet()) {
                int k = gcd(j, Math.abs(a[i]));
                int idx = tmap.get(j);
                if (segmentTree.containsKey(k)) {
                    int cur = segmentTree.get(k);
                    segmentTree.put(k, Math.min(idx, cur));
                } else {
                    segmentTree.put(k, idx);
                }
            }
            if (segmentTree.containsKey(Math.abs(a[i]))) {
                int j = segmentTree.get(Math.abs(a[i]));
                segmentTree.put(Math.abs(a[i]), Math.min(i, j));
            } else {
                segmentTree.put(Math.abs(a[i]), i);
            }
            tmap = segmentTree;
            tree.add(i, i, sum);

            Segment s = new Segment(i, i, a[i]);
            while (!dq.isEmpty() && dq.getLast().val <= a[i]) {
                tree.add(dq.getLast().left, dq.getLast().right, -dq.getLast().val);
                s.left = dq.getLast().left;
                dq.removeLast();
            }
            tree.add(s.left, s.right, s.val);
            dq.addLast(s);
            sum += a[i];
            for (int j : tmap.keySet()) {
                int pos = tmap.get(j);
                ans = Math.max(ans, j * (sum - tree.get(pos, i)));
            }
        }

        System.out.println(ans);
    }
}

class SegmentTree {
    private int n;
    private long[] min, add;

    SegmentTree(int size) {
        n = 1;
        while (n < size) {
            n *= 2;
        }
        min = new long[2 * n];
        add = new long[2 * n];
    }

    private void clear(int i, int l, int r) {
        min[i] = 0;
        add[i] = 0;
        if (l == r - 1) {
            return;
        }
        int tm = (l + r) / 2;
        clear(2 * i + 1, l, tm);
        clear(2 * i + 2, tm, r);
    }

    void clear(int n) {
        this.n = n;
        clear(0, 0, n);
    }

    private void push(int i, int tl, int tr) {
        min[i] += add[i];
        if (tl != tr - 1) {
            add[2 * i + 1] += add[i];
            add[2 * i + 2] += add[i];
        }
        add[i] = 0;
    }

    private void add(int i, int lt, int rt, int l, int r, long diff) {
        push(i, lt, rt);
        if (l >= rt || r <= lt) {
            return;
        }

        if (l <= lt && rt <= r) {
            add[i] += diff;
            push(i, lt, rt);
            return;
        }

        int tm = (lt + rt) / 2;
        add(2 * i + 1, lt, tm, l, r, diff);
        add(2 * i + 2, tm, rt, l, r, diff);
        min[i] = Math.min(min[2 * i + 1], min[2 * i + 2]);
    }

    private long get(int i, int lt, int rt, int l, int r) {
        push(i, lt, rt);
        if (l >= rt || r <= lt) {
            return Long.MAX_VALUE;
        }

        if (l <= lt && rt <= r) {
            return min[i];
        }

        int tm = (lt + rt) / 2;
        return Math.min(get(2 * i + 1, lt, tm, l, r), get(2 * i + 2, tm, rt, l, r));
    }

    void add(int l, int r, long diff) {
        add(0, 0, n, l, r + 1, diff);
    }

    long get(int l, int r) {
        return get(0, 0, n, l, r + 1);
    }
}


Problem solution in C++ programming.

#include <bits/stdc++.h>
using namespace std;
 
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define pconent(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

template<class T> struct MINRMQ {
    int n;
    vector<T> a;
    vector<vector<T> > f;

    T best(T a, T b) {
        return min(a, b);
    }
    void init(int n) {
        this->n = n;
        int p = 1; while ((1 << p) < n) p++;
        a.resize(n), f.resize(p + 1);
        for (int i = 0; i < (int) f.size(); i++) {
            f[i].resize(n);
        }
    }
    void upd(int u, T x) {
        a[u] = x;
    }
    void build() {
        for (int i = 0; i < n; i++) f[0][i] = a[i];
        for (int l = 0, k; (k = 1 << l) < n; l++) {
            for (int i = 0; i + k < n; i++) {
                f[l + 1][i] = best(f[l][i], f[l][i + k]);
            }
        }
    }
    T query(int a, int b) {
        int l = a == b ? 0 : __lg(b - a);
        return best(f[l][a], f[l][b - (1 << l) + 1]);
    }
};
template<class T> struct MAXRMQ {
    int n;
    vector<T> a;
    vector<vector<T> > f;

    T best(T a, T b) {
        return max(a, b);
    }
    void init(int n) {
        this->n = n;
        int p = 1; while ((1 << p) < n) p++;
        a.resize(n), f.resize(p + 1);
        for (int i = 0; i < (int) f.size(); i++) {
            f[i].resize(n);
        }
    }
    void upd(int u, T x) {
        a[u] = x;
    }
    void build() {
        for (int i = 0; i < n; i++) f[0][i] = a[i];
        for (int l = 0, k; (k = 1 << l) < n; l++) {
            for (int i = 0; i + k < n; i++) {
                f[l + 1][i] = best(f[l][i], f[l][i + k]);
            }
        }
    }
    T query(int a, int b) {
        int l = a == b ? 0 : __lg(b - a);
        return best(f[l][a], f[l][b - (1 << l) + 1]);
    }
};
template<class T> struct GCDRMQ {
    int n;
    vector<T> a;
    vector<vector<T> > f;

    T best(T a, T b) {
        return __gcd(abs(a), abs(b));
    }
    void init(int n) {
        this->n = n;
        int p = 1; while ((1 << p) < n) p++;
        a.resize(n), f.resize(p + 1);
        for (int i = 0; i < (int) f.size(); i++) {
            f[i].resize(n);
        }
    }
    void upd(int u, T x) {
        a[u] = x;
    }
    void build() {
        for (int i = 0; i < n; i++) f[0][i] = a[i];
        for (int l = 0, k; (k = 1 << l) < n; l++) {
            for (int i = 0; i + k < n; i++) {
                f[l + 1][i] = best(f[l][i], f[l][i + k]);
            }
        }
    }
    T query(int a, int b) {
        int l = a == b ? 0 : __lg(b - a);
        return best(f[l][a], f[l][b - (1 << l) + 1]);
    }
};
MINRMQ<long long> minrmq;
MAXRMQ<long long> maxrmq;
GCDRMQ<int> gcdrmq;

const int maxn = 1e6 + 5;
int n;
long long a[maxn];
long long b[maxn];
int l[maxn];
int r[maxn];

int getnext(int i, int u, int v) {
    int g = gcdrmq.query(u, v);
    int lo = v, hi = r[i];
    while (lo < hi) {
        int mi = lo + hi + 1 >> 1;
        if (gcdrmq.query(u, mi) == g) {
            lo = mi;
        }
        else {
            hi = mi - 1;
        }
    }
    return lo + hi >> 1;
}
int getprev(int i, int u, int v) {
    int g = gcdrmq.query(u, v);
    int lo = l[i], hi = u;
    while (lo < hi) {
        int mi = lo + hi >> 1;
        if (gcdrmq.query(mi, v) != g) {
            lo = mi + 1;
        }
        else {
            hi = mi;
        }
    }
    return lo + hi >> 1;
}

long long query1(int i, int u, int x, int y) {
    return gcdrmq.query(u, x) * (maxrmq.query(x, y) - b[u - 1] - a[i]);
}

long long query2(int i, int x, int y, int u) {
    return gcdrmq.query(y, u) * (b[u] - minrmq.query(x - 1, y - 1) - a[i]);
}

long long ff(int i, int u, int v) {
    return gcdrmq.query(u, v) * (b[v] - b[u - 1] - a[i]);
}

void solve() {
    cin >> n;
    FOR(i, 1, n + 1) cin >> a[i];
    partial_sum(a, a + n + 1, b);
    minrmq.init(n + 1);
    maxrmq.init(n + 1);
    gcdrmq.init(n + 1);
    FOR(i, 1, n + 1) minrmq.upd(i, b[i]);
    FOR(i, 1, n + 1) maxrmq.upd(i, b[i]);
    FOR(i, 1, n + 1) gcdrmq.upd(i, a[i]);
    minrmq.build();
    maxrmq.build();
    gcdrmq.build();
    FOR(i, 1, n + 1) l[i] = r[i] = i;
    FOR(i, 2, n + 1) {
        int ptr = i;
        while (ptr > 1 && a[i] >= a[ptr - 1]) ptr = l[ptr - 1];
        l[i] = ptr;
    }
    FORd(i, n, 1) {
        int ptr = i;
        while (ptr < n && a[i] > a[ptr + 1]) ptr = r[ptr + 1];
        r[i] = ptr;
    }
    long long res = -8 * LINF;
    FOR(i, 1, n + 1) {
        if (i - l[i] < r[i] - i) {
            FORd(j, i + 1, l[i]) {
                int ptr = i;
                while (ptr <= r[i]) {
                    int nptr = getnext(i, j, ptr);
                    chkmax(res, query1(i, j, ptr, nptr));
                    ptr = nptr + 1;
                }
            }
        }
        else {
            FOR(j, i, r[i] + 1) {
                int ptr = i;
                while (ptr >= l[i]) {
                    int nptr = getprev(i, ptr, j);
                    chkmax(res, query2(i, nptr, ptr, j));
                    ptr = nptr - 1;
                }
            }
        }
    }
    cout << res << "\n";
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    if (argc > 1) {
        assert(freopen(argv[1], "r", stdin));
    }
    if (argc > 2) {
        assert(freopen(argv[2], "wb", stdout));
    }
    solve();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


Problem solution in C programming.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define INF 200000
typedef struct _node
{
    int gcd;
    int max;
    long long sum;
}node;
typedef struct _tree_node
{
    enum
    {
        red, black
    }colour;
    int data;
    int real;
    struct _tree_node *left, *right, *parent;
}tree_node;
int a[50000], b[50000], nonzero[50000], rp[30], rc[30], treei[200000], rs, s, N;
long long ans, p[1000], tree[200000];
node t[200000];
tree_node *map[50000];
void getp(long long N, long long *prim)
{
    long long i, j, index = 2, flag;
    if( N <= 1 )
    {
        prim[0] = 0;
        return;
    }
    if( N == 2 )
    {
        prim[0] = 2;
        prim[1] = 0;
        return;
    }
    prim[0] = 2;
    prim[1] = 3;
    for( i = 5 ; i <= N ; i += 2 )
    {
        for( j = 1, flag = 1 ; prim[j] <= sqrt(i) ; j++ )
        {
            if( i % prim[j] == 0 )
            {
                flag = 0;
                break;
            }
        }
        if( flag == 1 )
        {
            prim[index] = i;
            index++;
        }
    }
    prim[index] = 0;
    return;
}
long long CC(long long n, long long d)
{
    if( n == 0 )
    {
        return d;
    }
    if( d == 0 )
    {
        return n;
    }
    while(1)
    {
        n = n % d;
        if( n == 0 )
        {
            return d;
        }
        d = d % n;
        if( d == 0 )
        {
            return n;
        }
    }
}
int max(int x, int y)
{
    return ( x > y ) ? x : y;
}
int min(int x, int y)
{
    return ( x < y ) ? x : y;
}
int abss(int x)
{
    return ( x < 0 ) ? -x : x;
}
int search(tree_node *root, int data)
{
    if(!root)
    {
        return INF;
    }
    if( root -> data == data )
    {
        return root -> real;
    }
    if( data < root -> data )
    {
        return search(root -> left, data);
    }
    return search(root -> right, data);
}
void left_rotate(tree_node **root, tree_node *x)
{
    tree_node *y;
    y = x -> right;
    if(!y)
    {
        return;
    }
    x -> right = y -> left;
    if(y -> left)
    {
        y -> left -> parent = x;
    }
    y -> parent = x -> parent;
    if( x -> parent == NULL )
    {
        *root = y;
    }
    else if( x == x -> parent -> left )
    {
        x -> parent -> left = y;
    }
    else
    {
        x -> parent -> right = y;
    }
    y -> left = x;
    x -> parent = y;
    return;
}
void right_rotate(tree_node **root, tree_node *y)
{
    tree_node *x;
    x = y -> left;
    if(!x)
    {
        return;
    }
    y -> left = x -> right;
    if(x -> right)
    {
        x -> right -> parent = y;
    }
    x -> parent = y -> parent;
    if( y -> parent == NULL )
    {
        *root = x;
    }
    else if( y == y -> parent -> right )
    {
        y -> parent -> right = x;
    }
    else
    {
        y -> parent -> left = x;
    }
    x -> right = y;
    y -> parent = x;
    return;
}
void reconstruct(tree_node **root, tree_node *x)
{
    tree_node *y, *z;
    y = x -> parent;
    z = x -> parent -> parent;
    x -> colour = black;
    z -> colour = red;
    x -> parent = z -> parent;
    if( z -> parent == NULL )
    {
        *root = x;
    }
    else if( z == z -> parent -> left )
    {
        z -> parent -> left = x;
    }
    else
    {
        z -> parent -> right = x;
    }
    if( z -> left == y )
    {
        x -> left = y;
        x -> right = z;
    }
    else
    {
        x -> left = z;
        x -> right = y;
    }
    y -> parent = z -> parent = x;
    y -> left = y -> right = z -> left = z -> right = NULL;
    return;
}
int normal_insert(tree_node **root, tree_node *x)
{
    if( *root == NULL )
    {
        *root = x;
    }
    else if( (*root) -> data == x -> data )
    {
        return 0;
    }
    else
    {
        x -> parent = *root;
        if( (*root) -> data > x -> data )
        {
            return normal_insert(&((*root) -> left), x);
        }
        else
        {
            return normal_insert(&((*root) -> right), x);
        }
    }
    return 1;
}
void insert(tree_node **root, tree_node *x)
{
    if(!normal_insert(root, x))
    {
        return;
    }
    tree_node *y;
    x -> colour = red;
    while( x != *root && x -> parent -> colour == red )
    {
        if( x -> parent == x -> parent -> parent -> left )
        {
            y = x -> parent -> parent -> right;
            if(!y)
                if( x == x -> parent -> left )
                {
                    x -> parent -> colour = black;
                    x -> parent -> parent -> colour = red;
                    right_rotate(root, x -> parent -> parent);
                }
                else
                {
                    y = x -> parent;
                    reconstruct(root, x);
                    x = y;
                }
            else if( y -> colour == red )
            {
                x -> parent -> colour = black;
                y -> colour = black;
                x -> parent -> parent -> colour = red;
                x = x -> parent -> parent;
            }
            else
            {
                if( x == x -> parent -> right )
                {
                    x = x -> parent;
                    left_rotate(root, x);
                }
                x -> parent -> colour = black;
                x -> parent -> parent -> colour = red;
                right_rotate(root, x -> parent -> parent);
            }
        }
        else
        {
            y = x -> parent -> parent -> left;
            if(!y)
                if( x == x -> parent -> right )
                {
                    x -> parent -> colour = black;
                    x -> parent -> parent -> colour = red;
                    left_rotate(root, x -> parent -> parent);
                }
                else
                {
                    y = x -> parent;
                    reconstruct(root, x);
                    x = y;
                }
            else if( y -> colour == red )
            {
                x -> parent -> colour = black;
                y -> colour = black;
                x -> parent -> parent -> colour = red;
                x = x -> parent -> parent;
            }
            else
            {
                if( x == x -> parent -> left )
                {
                    x = x -> parent;
                    right_rotate(root, x);
                }
                x -> parent -> colour = black;
                x -> parent -> parent -> colour = red;
                left_rotate(root, x -> parent -> parent);
            }
        }
    }
    (*root) -> colour = black;
    return;
}
void merge(int *a, int *left, int *right, int left_size, int right_size, int *new_size)
{
    int i = 0, j = 0, index = 0;
    while( i < left_size || j < right_size )
    {
        if( i == left_size )
        {
            a[index++] = right[j];
            j++;
        }
        else if( j == right_size )
        {
            a[index++] = left[i];
            i++;
        }
        else if( left[i] <= right[j] )
        {
            a[index++] = left[i];
            i++;
        }
        else
        {
            a[index++] = right[j];
            j++;
        }
        if( index > 1 && a[index-2] == a[index-1] )
        {
            index--;
        }
    }
    (*new_size) = index;
    return;
}
void init(int n)
{
    N = 1;
    while( N < n )
    {
        N *= 2;
    }
    for( int i = 1 ; i < N + n ; i++ )
    {
        tree[i] = -1000000000000000000LL;
    }
}
int range_sum(int i, int j)
{
    int ansi;
    long long ans = -1000000000000000000LL;
    for( i += N, j += N ; i <= j ; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
    {
        if( i % 2 == 1 )
            if( tree[i] > ans )
            {
                ans = tree[i];
                ansi = treei[i];
            }
        if( j % 2 == 0 )
            if( tree[j] > ans )
            {
                ans = tree[j];
                ansi = treei[j];
            }
    }
    return ansi;
}
void update(int i, long long val)
{
    int j;
    for( j = i + N ; j ; j /= 2 )
        if( val > tree[j] )
        {
            tree[j] = val;
            treei[j] = i;
        }
}
void sort_a(int *a, int size, int *new_size)
{
    if( size < 2 )
    {
        (*new_size) = size;
        return;
    }
    int m = ( size + 1 ) / 2, i;
    int *left, *right;
    left = (int*)malloc(m * sizeof(int));
    right = (int*)malloc(( size - m ) * sizeof(int));
    for( i = 0 ; i < m ; i++ )
    {
        left[i] = a[i];
    }
    for( i = 0 ; i < size - m ; i++ )
    {
        right[i] = a[i+m];
    }
    int new_l_size = 0, new_r_size = 0;
    sort_a(left, m, &new_l_size);
    sort_a(right, size-m, &new_r_size);
    merge(a, left, right, new_l_size, new_r_size, new_size);
    free(left);
    free(right);
    return;
}
long long query(int v, int tl, int tr, int l, int r, int *gcd, int *ma, long long *sum)
{
    int tm, g1, g2, m1, m2;
    long long s1, s2;
    if( tl > r || tr < l )
    {
        *gcd = 0;
        *ma = 0;
        *sum = 0;
        return 0;
    }
    if( tl >= l && tr <= r )
    {
        *gcd = t[v].gcd;
        *ma = t[v].max;
        *sum = t[v].sum;
        return (*gcd) * ( (*sum) - (*ma) );
    }
    tm = ( tl + tr ) / 2;
    query(2*v, tl, tm, l, r, &g1, &m1, &s1);
    query(2*v+1, tm+1, tr, l, r, &g2, &m2, &s2);
    *gcd = CC(g1, g2);
    *ma = max(m1, m2);
    *sum = s1 + s2;
    return (*gcd) * ( (*sum) - (*ma) );
}
void solve(int start, int bs, int ns)
{
    int gcd, ma, i, j;
    long long t, sum;
    for( i = 0 ; i < bs ; i++ )
    {
        if( b[i] == ns )
        {
            continue;
        }
        if( i == bs - 1 )
        {
            j = range_sum(b[i], ns-1);
        }
        else
        {
            j = range_sum(b[i], b[i+1]-1);
        }
        t = query(1, 0, ns-1, start, j, &gcd, &ma, &sum);
        if( t > ans )
        {
            ans = t;
        }
    }
    return;
}
void copy_tree(tree_node **d, tree_node *r)
{
    tree_node *p;
    if(!r)
    {
        return;
    }
    copy_tree(d, r->left);
    p = (tree_node*)malloc(sizeof(tree_node));
    p -> data = r -> data;
    p -> real = r -> real;
    p -> left = p -> right = p -> parent = NULL;
    insert(d, p);
    b[s++] = r -> real + 1;
    copy_tree(d, r -> right);
    return;
}
void build(int v, int tl, int tr)
{
    int tm;
    if( tl == tr )
    {
        t[v].gcd = abss(a[tl]);
        t[v].max = t[v].sum = a[tl];
    }
    else
    {
        tm = ( tl + tr ) / 2;
        build(2*v, tl, tm);
        build(2*v+1, tm+1, tr);
        t[v].gcd = CC(t[2*v].gcd, t[2*v+1].gcd);
        t[v].max = max(t[2*v].max, t[2*v+1].max);
        t[v].sum = t[2*v].sum + t[2*v+1].sum;
    }
    return;
}
int main()
{
    int n, x, ns, i, j, k, l;
    long long sum;
    tree_node *last_node, *p_node;
    getp(1000, p);
    scanf("%d", &n);
    for( i = 0 ; i < n ; i++ )
    {
        scanf("%d", a + i);
    }
    build(1, 0, n-1);
    init(n);
    for( i = sum = 0 ; i < n ; i++ )
    {
        sum += a[i];
        update(i, sum);
    }
    for( i = n - 1 ; i >= 0 ; i-- )
    {
        if( i == n - 1 )
        {
            last_node = NULL;
        }
        else
        {
            last_node = map[i+1];
        }
        if(a[i])
        {
            nonzero[i] = i;
            for( j = rs = 0, x = abss(a[i]) ; p[j] && p[j] * p[j] <= x ; j++ )
            {
                if( x % p[j] == 0 )
                {
                    rp[rs] = p[j];
                    rc[rs] = 0;
                    while( x % p[j] == 0 )
                    {
                        rc[rs]++;
                        x /= p[j];
                    }
                    rs++;
                }
            }
            if( x != 1 )
            {
                rp[rs] = x;
                rc[rs] = 1;
                rs++;
            }
            for( j = s = 0 ; j < rs ; j++ )
            {
                for( k = 0, x = rp[j] ; k < rc[j] ; k++, x *= rp[j] )
                {
                    p_node = (tree_node*)malloc(sizeof(tree_node));
                    p_node -> data = x;
                    p_node -> left = p_node -> right = p_node -> parent = NULL;
                    l = search(last_node, x);
                    if( l != INF )
                    {
                        p_node -> real = l;
                        b[s++] = l + 1;
                    }
                    else
                    {
                        p_node -> real = i;
                    }
                    insert(&map[i], p_node);
                }
            }
            b[s++] = i;
            sort_a(b, s, &ns);
            solve(i, ns, n);
        }
        else
        {
            nonzero[i] = INF;
            s = 0;
            copy_tree(&map[i], last_node);
            if( i != n - 1 && nonzero[i+1] != INF )
            {
                b[s++] = nonzero[i+1];
            }
            sort_a(b, s, &ns);
            solve(i, ns, n);
        }
        if( i != n - 1 )
        {
            nonzero[i] = min(nonzero[i], nonzero[i+1]);
        }
    }
    printf("%lld", ans);
    return 0;
}