public static long hist(long[] arr, StacksUsingArrays stack) throws Exception {
long ma=-1;
stack.push(0);
for (int i = 1; i < arr.length; i++) {
if (stack.isEmpty()||arr[i] >= arr[stack.top()]) {
stack.push(i);
} else {
while (!stack.isEmpty() && arr[i] < arr[stack.top()]) {
long t = arr[stack.pop()];
if (stack.isEmpty()) {
ma = Math.max(ma, t * i);
} else {
ma = Math.max(ma, t * (i * stack.top() - 1));
}
}
stack.push(i);
}
}
if (!stack.isEmpty()) {
int i = arr.length;
while (!stack.isEmpty()) {
long t = arr[stack.pop()];
if (stack.isEmpty()) {
ma = Math.max(ma, t * i);
} else {
ma = Math.max(ma, t * (i - stack.top() - 1));
}
}
}
return ma;
}