/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
// An efficient method to calculate
// stock span values implementing the
// same idea without using stack
static void calculateSpan(int A[],
int n, int ans[])
{
// Span value of first element is always 1
ans[0] = 1;
// Calculate span values for rest of the elements
for (int i = 1; i < n; i++) {
int counter = 1;
printArray(A, i);
while ((i - counter) >= 0 && A[i] > A[i - counter]) {
counter += ans[i - counter];
}
ans[i] = counter;
}
}
// A utility function to print elements of array
static void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.
out.
print(arr
[i
] + " "); }
// Driver code
public static void main
(String[] args
) {
int price[] = { 10, 4, 5, 90, 120, 80 };
int n = price.length;
int S[] = new int[n];
// Fill the span values in array S[]
calculateSpan(price, n, S);
// print the calculated span values
printArray(S, n);
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCS8vIEFuIGVmZmljaWVudCBtZXRob2QgdG8gY2FsY3VsYXRlIAogICAgLy8gc3RvY2sgc3BhbiB2YWx1ZXMgaW1wbGVtZW50aW5nIHRoZSAKICAgIC8vIHNhbWUgaWRlYSB3aXRob3V0IHVzaW5nIHN0YWNrIAogICAgc3RhdGljIHZvaWQgY2FsY3VsYXRlU3BhbihpbnQgQVtdLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW50IG4sIGludCBhbnNbXSkgCiAgICB7IAogICAgICAgIC8vIFNwYW4gdmFsdWUgb2YgZmlyc3QgZWxlbWVudCBpcyBhbHdheXMgMSAKICAgICAgICBhbnNbMF0gPSAxOyAKICAKICAgICAgICAvLyBDYWxjdWxhdGUgc3BhbiB2YWx1ZXMgZm9yIHJlc3Qgb2YgdGhlIGVsZW1lbnRzIAogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDwgbjsgaSsrKSB7IAogICAgICAgICAgICBpbnQgY291bnRlciA9IDE7IAogICAgICAgICAgICBwcmludEFycmF5KEEsIGkpOwogICAgICAgICAgICB3aGlsZSAoKGkgLSBjb3VudGVyKSA+PSAwICYmIEFbaV0gPiBBW2kgLSBjb3VudGVyXSkgeyAKICAgICAgICAgICAgICAgIGNvdW50ZXIgKz0gYW5zW2kgLSBjb3VudGVyXTsgCiAgICAgICAgICAgIH0gCiAgICAgICAgICAgIGFuc1tpXSA9IGNvdW50ZXI7IAogICAgICAgIH0gCiAgICB9IAogIAogICAgLy8gQSB1dGlsaXR5IGZ1bmN0aW9uIHRvIHByaW50IGVsZW1lbnRzIG9mIGFycmF5IAogICAgc3RhdGljIHZvaWQgcHJpbnRBcnJheShpbnQgYXJyW10sIGludCBuKSAKICAgIHsgCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIAogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50KGFycltpXSArICIgIik7IAogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigpOyAKICAgIH0gCiAgCiAgICAvLyBEcml2ZXIgY29kZSAKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIAogICAgeyAKICAgICAgICBpbnQgcHJpY2VbXSA9IHsgMTAsIDQsIDUsIDkwLCAxMjAsIDgwIH07IAogICAgICAgIGludCBuID0gcHJpY2UubGVuZ3RoOyAKICAgICAgICBpbnQgU1tdID0gbmV3IGludFtuXTsgCiAgCiAgICAgICAgLy8gRmlsbCB0aGUgc3BhbiB2YWx1ZXMgaW4gYXJyYXkgU1tdIAogICAgICAgIGNhbGN1bGF0ZVNwYW4ocHJpY2UsIG4sIFMpOyAKICAKICAgICAgICAvLyBwcmludCB0aGUgY2FsY3VsYXRlZCBzcGFuIHZhbHVlcyAKICAgICAgICBwcmludEFycmF5KFMsIG4pOyAKICAgIH0gCn0=