### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

If the result is of form **444…444 or 777…777** then any operation will not change the result, so we can try these cases separetely.

We can iterate integer **x** from 1 to **n**, for which **s[x] = 4**. We assume that digit in position **x** will be the last digit **4** of the result. If we do not want to make operation, the result for current **x** will be **c4[x]+c7[x]**, where **c4[x]** is the number of digits **4** in **s[1…x]** and **c7[x]** is the number of digits **7** in **s[x+1…n]**. But we can try to improve that result by making a single operation. Let pair of integers **(l, r)** to be the chosen string before operation. We’ll consider that **l <= x** (other case is the simmetrical to current). In this case there are also two cases.

First is if **r < x**: if we choose such substring (**l, r)**, of course, we need to transfer it to the right of **x** (because in other case we’ll not improve the result). Let **d4** be the number of digits **4** the **s[l…r]** and **d7** be the number of **7** in **s[l…r]**. After transfering **s[l…r]** exactly **d4** will be subtracted from result for **x**, and exactly **d7** will be added. So we just need to find such pair **(l, r), 1 <= l <= r < x** that **d7-d4** is maximum possible.

Second case is if **r >= x**, i. e. current **x** will be at the substring that we choose (because **l <= x and r >= x)**. You can notice that this case is actually the same like the first one. For example: let we have string **474474474777** and we choose the substring **474474[4747]77** and move it to **47[4747]447477**. You can see that it is the same like to choose **47[4474]474777** and move it to **474747[4474]77**. So we do not need to consider this case at all.

Now the problem is to find for all x maximum **d7-d4** of all pairs **(l, r), 1 <= l <= r < x**, call it **F[x]**. Since we are iterating x from left to right, **F[x] >= F[x-1]**, i. e. before **x-th** iteration we consider **F[x] = F[x-1]**, but there may be better segment for which **r = x**. To find it we define **t7[i]** as the number of digits **7** in **s[1…i]** and **t4[i]** as the number of digits **4** in **s** **[1…i]**. We need to maximize **d7-d4**, rewrite it as **(t7[x]-t7[l])-(t4[x]-t4[l]) => t7[x]-t7[l]-t4[x]+t4[l] => t7[x]-t4[x] - t7[l]+t4[l]**. Since x is fixed we need to find such l that **t4[l]-t7[l]** is maximized. We can just keep it as a global parametr and refresh after each iteration of **x**.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.