### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

Any state of the array can be represented as a binary mask with each bit **1** means that corresponding number is equal to the **max** and **0** otherwise. You can run DP with state **R[mask]** and **O(n)** transits. You can proof (or just believe) that the number of statest will be not big, of course if you run good **DP**. The state of our DP will be the mask of numbers that are equal to **max**. Of course, it makes sense to use operation only for such subarray **[l; r]** that number of **1**-bits is at least as much as number of **0**-bits in submask [l; r], because otherwise nothing will change. Also you should notice that if the left bound of your operation is l it is good to make operation only with the maximal possible **r** (this gives number of transits equal to **O(n)**). It was also useful for **C++** coders to use **map** structure to represent all states.

### SETTERâ€™S SOLUTION

Can be found here.

### TESTERâ€™S SOLUTION

Can be found here.