# Easy Peasy, Lemon Squeezy

Dummy Programming Contest...

For subtask 1, we can keep an array and can traverse the whole array for minimum and maximum. Worst case complexity will be O(n2).

For subtask 2, we can keep a multiset and add/erase dataset with a log factor. As, set is already sorted, we can find minimum and maximum in O(1). So, worst case complexity will be O(n log(n)).

As the removal is from back, we don't need to consider smaller elements while finding maximum element & larger elements while finding the minimum. How?
Lets, we have A = [5], then adding 1, 2, 3, 4, 5 etc don't have an effect on maximum. The maximum is still 5 after addition or removal from the back until we have to remove 5. So, instead of adding new element in the back, we can add current maximum, i.e. 5. If a value greater than 5 comes then we'll start adding the larger value from now on. For example, we have [5, 1, 2, 3, 4, 5, 7] to add one after another. Our maximum array will be [5, 5, 5, 5, 5, 7]. To find maximum we have to check the last element of the array.

We have to do the same for the minimum. Let's think we have A = [2], then adding 2, 3, 4, 5 etc don't have an effect on minimum. The minimum is still 2 after addition or removal from the back until we have to remove 2. So, instead of adding new element in the back, we can add current minimum, i.e. 2. If a value less than 2 comes then we'll start adding the smaller value from now on. For example, we have [2, 3, 4, 5, 1] to add one after another. Our minimum array will be [2, 2, 2, 2, 1]. To find minimum we have to check the last element of the array.

So to do this, we need a data structure that can remove element in O(1) from the back/top of the array. We can use stack for this. We need two separate stacks for minimum and maximum. The addition and finding max/min is done in O(1), so we can solve this problem in input time.

### Statistics

54% Solution Ratio
Samin_SieyamEarliest, Jun '20
defaltFastest, 0.3s
YouKnowWhoLightest, 78 MB
NirjhorShortest, 594B