**Problem link** : contest practice

**Difficulty** : Easy

**Pre-requisites** : Two pointers

**Problem** : Calculate the minimum possible penalty for the game described.

**Explanation** :

The heart of the solution is the following idea:

Let’s say that all the cells with the value of **A _{i}** greater than some

**K**are prohibited ones and we can’t use them. Then, we need to find a such way from

**0**to

**N+1**that minimizes the maximal value of

**B**where

_{y}**y**is the index of some visited cell. Let’s call this minimal value

**F**

_{K}Let’s check all the possible values of **K**, namely from **0** to **32000**. It is clear that while increasing the value of **K** some cells stop being prohibited, and therefore the value of **F _{K}** will only decrease. This gives rise to the two-pointers solution:

Initially, all the cells are prohibited. We iterate our **K** from **0** to **32000**. When **K** gets increased, some new cells with the value of **A** equal to **K** stop being prohibited. But then, we might be able to make some cells prohibited again, and this time, forever. More precisely, when there exists a path from **0** to **N+1**, we just pick some non-prohibited cell with currently the maximal value of **B** and if there will still be a path from **0** to **N+1**, then we delete it. Otherwise, we just stop the deletion, try to improve the answer and proceed the cycle. To check, whether there is a path, it is necessary to find the largest distance between any two adjacent currently non-prohibited cells and to compare it to **K**.

But how to make the cells prohibited/non-prohibited and to find all the distances? STL does well here. We can store the indexes of currently non-prohibited cells in the set, as well as pairwise differences between adjacent non-prohibited cells. In order to pick a non-prohibited cell with the maximal value of **B**, we can use the priority queue.

This gives us **O(N log N)** solution.