The Beautiful sequence

Statement

Goal

We define the beautiful value of an integer sequence as the product of the value of its smallest element and its length. You are given an integer sequence containing N elements, and you should find out one of its continuous subsequences, such that it has the largest beautiful value among all the continuous subsequences.

You may solve this problem with an O(N) algorithm.

Input

Line 1: A single integer N, indicating the length of the sequence.
Line 2: N integers indicating the sequence.

Output

Line 1: The largest beautiful value you can find. (Note you don't need to output the subsequence itself.)

Constraints

1 <= N <= 500
The value of the elements is between 0 and 10000, inclusive.

Example

Input

3
1 2 3

Output

Tags

Sequences

Difficulty

Hard

Test cases

Sample Test

Input

3 1 2 3

Output

Validator 1 Validator

Input

3 3 2 1

Output

Only one element Test

Input

1 0

Output

Validator 2 Validator

Input

1 10000

Output

10000

All the same Test

Input

7 24 24 24 24 24 24 24

Output

168

Validator 3 Validator

Input

7 233 233 233 233 233 233 233

Output

1631

A larger testdata Test

Input

25 6432 2878 3540 409 3682 7028 7752 2353 224 503 8255 5232 699 5298 6395 4951 9083 1709 5724 8799 1997 523 1034 6500 2467

Output

19804

Validator 4 Validator

Input

25 6788 7572 7421 1870 3858 9057 9328 959 512 5725 2134 32 9007 6608 509 7025 5891 8445 8665 4318 1103 6776 2015 7426 8562

Output

23564

Increasing sequence Test

Input

15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Output

Validator 5 Validator

Input

15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5

Output

The largest testcase Test

Input

200 938 963 2208 2365 2799 3015 3871 4143 4196 5020 5839 6175 6381 6548 6690 6698 6738 8138 8938 9968 9968 8938 8138 6738 6698 6690 6548 6381 6175 5839 5020 4196 4143 3871 3015 2799 2365 2208 963 938 938 963 2208 2365 2799 3015 3871 4143 4196 5020 5839 6175 6381 6548 6690 6698 6738 8138 8938 9968 9968 8938 8138 6738 6698 6690 6548 6381 6175 5839 5020 4196 4143 3871 3015 2799 2365 2208 963 938 938 963 2208 2365 2799 3015 3871 4143 4196 5020 5839 6175 6381 6548 6690 6698 6738 8138 8938 9968 9968 8938 8138 6738 6698 6690 6548 6381 6175 5839 5020 4196 4143 3871 3015 2799 2365 2208 963 938 938 963 2208 2365 2799 3015 3871 4143 4196 5020 5839 6175 6381 6548 6690 6698 6738 8138 8938 9968 9968 8938 8138 6738 6698 6690 6548 6381 6175 5839 5020 4196 4143 3871 3015 2799 2365 2208 963 938 938 963 2208 2365 2799 3015 3871 4143 4196 5020 5839 6175 6381 6548 6690 6698 6738 8138 8938 9968 9968 8938 8138 6738 6698 6690 6548 6381 6175 5839 5020 4196 4143 3871 3015 2799 2365 2208 963 938

Output

187600

Validator 6 Validator

Input

200 137 969 1101 1109 1618 1714 2068 2218 2527 2735 3289 4102 5169 5313 6914 7223 8084 8794 9154 9693 9693 9154 8794 8084 7223 6914 5313 5169 4102 3289 2735 2527 2218 2068 1714 1618 1109 1101 969 137 137 969 1101 1109 1618 1714 2068 2218 2527 2735 3289 4102 5169 5313 6914 7223 8084 8794 9154 9693 9693 9154 8794 8084 7223 6914 5313 5169 4102 3289 2735 2527 2218 2068 1714 1618 1109 1101 969 137 137 969 1101 1109 1618 1714 2068 2218 2527 2735 3289 4102 5169 5313 6914 7223 8084 8794 9154 9693 9693 9154 8794 8084 7223 6914 5313 5169 4102 3289 2735 2527 2218 2068 1714 1618 1109 1101 969 137 137 969 1101 1109 1618 1714 2068 2218 2527 2735 3289 4102 5169 5313 6914 7223 8084 8794 9154 9693 9693 9154 8794 8084 7223 6914 5313 5169 4102 3289 2735 2527 2218 2068 1714 1618 1109 1101 969 137 137 969 1101 1109 1618 1714 2068 2218 2527 2735 3289 4102 5169 5313 6914 7223 8084 8794 9154 9693 9693 9154 8794 8084 7223 6914 5313 5169 4102 3289 2735 2527 2218 2068 1714 1618 1109 1101 969 137

Output

82968

Larger than largest yet smaller Test

Input

498 7 5 0 4 5 9 5 7 9 7 6 4 5 4 8 3 6 0 4 5 2 4 2 2 2 1 3 6 5 0 0 7 3 9 7 2 9 1 9 8 9 3 6 0 2 6 5 1 8 9 5 0 0 5 6 4 3 6 8 2 3 6 3 6 5 6 9 3 3 9 0 3 1 5 6 8 7 7 8 3 7 5 4 7 0 8 5 5 0 9 3 5 8 1 6 9 3 3 6 7 0 0 6 8 0 8 0 2 8 9 6 0 4 2 9 1 0 5 8 3 0 4 4 1 0 6 9 8 2 8 4 7 5 6 5 9 0 4 5 4 5 1 2 2 7 4 5 7 2 4 2 7 7 3 5 3 1 7 4 9 4 8 6 1 1 5 6 7 5 6 8 1 4 8 7 3 4 6 2 9 9 5 2 6 9 7 9 8 4 1 3 9 1 5 1 4 6 4 2 2 9 8 3 5 7 9 3 4 8 6 2 1 8 0 1 7 4 7 6 3 5 9 7 7 8 4 6 8 5 8 8 8 4 2 3 2 3 5 2 1 9 5 7 0 1 5 5 7 2 5 7 0 8 6 7 1 7 1 4 8 8 6 0 7 4 8 4 3 8 1 0 5 7 8 2 9 7 6 0 6 9 2 7 3 2 5 1 3 2 5 1 0 0 9 3 3 3 0 0 6 2 1 2 6 1 4 1 9 5 5 9 1 8 9 8 6 6 6 0 6 2 7 2 2 2 5 4 0 2 5 5 2 5 8 9 4 2 5 1 9 6 4 6 2 4 1 9 2 6 3 1 9 4 8 0 7 8 9 9 8 0 5 6 4 9 2 2 8 9 5 9 1 2 5 3 7 4 6 1 4 3 4 2 9 1 5 1 6 8 0 7 4 7 9 3 9 0 1 4 2 4 3 7 4 4 8 4 0 9 7 3 1 5 9 3 2 2 8 7 6 9 0 5 6 4 0 2 1 4 2 3 1 8 0 5 2 7 1 7 5 9 1 9 1 2 1 7 9 0 5 9 2 6 0 6 9 9 1 3 3 9 7 8 8 6 7 3 4 1 6 0 4 7 8 6 5 0 9 9 6 7 8 5 9 4 4 4 4 5 1 1 7 5 5 9 5 9 8

Output

Validator 7 Validator

Input

498 7 9 0 9 1 6 9 6 3 5 3 1 2 4 0 1 6 5 8 3 2 1 8 0 3 9 5 6 4 3 0 8 5 6 7 7 3 3 9 0 9 0 3 6 8 3 3 5 4 0 0 0 6 9 0 0 3 7 6 5 1 8 2 1 1 2 5 3 3 9 1 8 2 9 9 9 5 6 7 8 0 1 3 5 2 5 7 3 5 8 4 5 6 6 6 1 6 1 8 8 4 0 8 4 3 9 4 0 3 1 4 5 1 2 6 7 7 6 0 7 5 4 0 4 4 2 9 6 2 6 0 9 4 5 9 1 0 3 3 3 8 3 4 5 7 9 5 5 6 3 0 0 1 1 9 3 4 0 1 6 8 2 5 5 0 2 8 7 5 7 5 2 5 3 3 6 1 9 5 9 1 1 0 5 5 9 3 7 9 2 7 3 9 9 8 5 1 7 7 1 7 7 5 2 9 8 8 8 5 4 7 0 8 4 7 7 5 9 2 0 9 7 6 0 3 9 0 5 4 5 7 7 1 0 1 5 2 7 3 4 0 6 5 1 4 9 8 7 3 8 1 0 3 0 6 2 1 8 9 6 1 7 2 6 1 8 5 6 0 3 5 6 8 8 7 4 2 2 8 7 9 0 1 4 2 2 7 6 7 5 1 0 7 5 0 3 2 0 4 3 4 9 8 0 8 1 8 7 3 7 1 8 5 4 4 3 8 1 4 5 4 9 1 7 5 8 0 3 9 0 2 4 8 8 8 9 0 4 1 9 1 0 5 3 7 6 0 2 2 3 7 3 7 4 8 0 2 5 9 8 1 6 8 9 1 1 2 1 8 7 2 0 1 4 6 5 7 6 0 3 4 6 0 8 8 8 5 7 7 9 5 6 6 1 7 2 2 6 8 2 1 5 7 0 6 4 3 3 1 8 0 8 5 2 0 2 9 3 7 3 6 6 0 0 2 7 3 1 0 3 1 8 7 7 7 3 3 1 3 7 4 3 6 6 1 5 7 9 2 9 8 9 9 0 2 7 2 6 7 4 9 6 3 6 7 3 5 1 4 5 3 4 0 3 1 2 5 6 0 2 7 2 4 4 6 1 0 3 1 4 0 8 0 7 8 9 7 3

Output

Solution language

Solution

Stub generator input

Comments

23 Comments

5DN1L Unnamed CodinGamer

about 2 months ago

I've just made the following changes: Goal * Changed "Please" to "You may" because there's no way to enforce the rule. Constraints * Changed 100000 to 500 as the maximum value of [[N]] in the cases is just 498. Tags * Added the tag "Sequences".

JBM Unnamed CodinGamer

over 8 years ago

I'm not quite sure what "continuous" means in a sequence context.

Never mind, seems to be the norm in the angloCSosphere. Eerily close to Flood the world. But way cleaner in the end. Approved. But someone, someday, is going to complain that that it should say N <= 200. Which makes me think, I haven't checked whether it was still bruteforceable. Edit: yup, bruteforceable.

superredlark Unnamed CodinGamer

Your O(N) implement is nice. I changed your constraints to [1, 100000] and add some comment to indicate this is an O(N) problem. It's OK that the largest test case only have 200 numbers, I think.

magaiti Unnamed CodinGamer

about 9 years ago

With current data sizes can be easily bruteforced even as O(n^2), in a few lines of code. If you want really long sequences, I suggest specifying a RNG algorithm, and providing sequence length and seed as input. Linear congruential generators are very concise (literally up to one line of code). You can define the RNG as a pseudocode in your statement, like it is done in Nintendo Challenge.

dogther Unnamed CodinGamer

Thanks for the advice. However, if I use RNG, it means I can't design the data myself. For example, a bruteforced algorithm with some simple prunning can pass the random data easily. (So I'm just wondering if there can be a function to add larger test data? Or to generate the data by code, like codeforces' hacks?)

nicola Unnamed CodinGamer

I don’t understand. Is a beautiful value of the sequence u a n such that u(n)=n? How are the sequences defined exactly?

"product" means "multiply"