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].
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 << "msn";
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;
}