### PROBLEM LINKS

### DIFFICULTY

EASY

### EXPLANATION

Let **c4[i]** be the number of digits **4** among all digits in **S[1, i]** and **c7[i]** be the number of digits **7** among all digits in **S[1, i]**. Formally, you need to find the number of such pairs **(L; R)** that there exists at least one **i (L <= i+1 <= R)** such that **c4[i]-c4[L-1] = c7[R]-c7[i]** (here **i+1** plays the role of **X** from the definition in the problem statement). Rewrite this equation as **ñ4[i]+c7[i]-c4[L-1] = c7 [R]**. Now you can notice, that actually **c4[i]+c7[i] = i** (recall that the numeration of characters starts from 1). So now **i-c4[L-1]** should be equal to **c7[R]**. Rewrite it as **c7[R]+c4[L-1] = i**. Iterate all **L** from **1** to **N**, now you need to find for fixed **L** the number of good **R**. Since **L <= i+1 <= R** you need to find the number of such **R** that **L <= c7[R]+c4[L-1]+1 <= R**. Note, that **c7[R]+c4[L- 1]+1** is always greater than or equal to **L**, so restriction is just **c7[R]+c4[L-1]+1 <= R**. Rewrite it as

**c4[L-1]+1 <= R-c7[R].** (1)

So the problem now is to find the number of such **R** **(R >= L)** that **R-c7[R]** is greater than or equal to **c4[L-1]+1**. This can be done using BIT (Binary Index Tree) (use Google to find information about that). Consider the array **C, C[i]** is the current number of such **R** that **R-c7[R] = i**. It will be updated during the pass by all **L**. Namely, we start from **L = N** and will decrease **L** by 1 at each step while **L >= 1**. At each step we at first increase value **C[L-C7[L]]** by 1. So array **C** will contain information about all **R >= L** and hence the number of good **R** for the current **L** can be simply found as the sum of **C[i]** for **c4[L-1]+1 <= i <= N.** BIT allows to do both operations (change and query) in **O(log N**). So we obtain the **O(N log N)** solution.

But such solution will be an overrun for this problem. There exists much simpler solution. Just notice, that the only strings that are not balanced are the strings that do not have digits **4**, that is, the strings of the form **777…777** of any positive length. Next we present the proof of this fact. Even two proofs :). Choose the one you are more comfortable with.

**Proof of the author**. Let pair of integers **(a, b)** for some position **x** is the balance pair for **x**, i. e. **a** is equal to the number of digits **4** in **S[1, x-1]** and b is the number of digits **7** in **S[x, N]**. We need to find such **x** that **a-b = 0** for that position. For **x = 1** pair **(a, b)** is **(0, c7)**, and for **x = N** this pair is **(c4-1, 0)** if the last digit is **4** and **(c4, 1)** if the last digit is **7**, where **c4** and **c7** is the total number of corresponding digits in **S**. When you are iterating **x** from left to right, pair **(a, b)** turns either to **(a+1, b)** or to **(a, b-1)**. During all N iterations of **x**, **(0, c7)** will be turned to **(c4-1, 0)** (or **(c4, 1))**. Since a increases by **0** or **1** and **b** decreases by **0** or **1** at each step, the case **a = b** will happen for some **x**, in general. But the only string that sucks is the string of the form mentioned above. In that case pair **(0, c7)** will be turned to pair **(0, 1)** by only decreasing **c7**. Hence there will be no **x** such that **a = b** for that **x**.

**Proof of the tester.** Let S be some lucky string of the length **N**. Denote by **L4(x)** the number of digits **4** in the substring **S[1, x-1]** and by **R7(x)** the number of digits **7** in the substring **S[x, N]**. Consider the difference **D(x) = L4(x) - R7(x)** as a function of **x**. According to the definition, the string **S** is balanced if and only if **D(x) = 0** for some **x** with **1 <= x <= N**. Try to analyze the behavior of this function. Note that, **D(1) = -n7 <= 0** where **n7** is the total number of digits **7** in the string **S**. Further note, that **D(N) = n4’** if **S[N] = 4** and **D(N) = n4’ - 1 if S[N] = 7**. Here **n4’** is the number of digits strong text **4** in the substring **S[1, N-1]** (so we ignore last character of **S**). Note that **D(N) < 0** if and only if **n4’ = 0** and **S[N] = 7**, that is, if **S** does not have digits **4**. We will use this important observation later. Now we analyze how **D(x)** changes when **x** is increasing by **1**. If S[x] = **4** then **L4(x+1) = L4(x) + 1** and **R7(x+1) = R7(x)**. So in this case **D(x+1) = D(x) + 1**. Similarly if **S[x]** = **7** we see that **D(x+1) = D(x) + 1.** Thus, **D(x+1) = D(x) + 1** for all **x**. Consider the case when **D(N) >= 0**, that is, the case when **S** contains at least one digit **4**. Then, conditions **D(1) <= 0, D(x+1) = D(x) + 1 for 1 <= x <= N-1** and **D(N) >= 0** implies that **D(x) = 0** for some x. Thus, the string that has at least one digit **4** is always balanced. On the other hand, it is easy to see that if S is composed of exactly **N** digits **7** then **D(x) = x-1-N < 0 for 1 <= x <= N**. So such string is not balanced. This finishes the proof.

This means that you just need to find the number of non-balanced substrings, and it is the number of such **(L; R), 1 <= L <= R <= N that s[x] = 7 for L <= x <= R.** And this is the simple problem which is the homework for you

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.