We can read in the integer as a string, and count the total number of '4' and '7'. As the length of string is at most 18, it is sufficient to check whether the total number is 4 or 7.

One can find that the optimal sequence should have pattern 'abcdabcdabcd...', and thus we can just output the first *n* letters.

Suppose that the minimum integer has *x* 4s and *y* 7s. Then, we have 4*x* + 7*y* = *n*. To construct the minimum integer, we must have *x* + *y* as small as possible. If there are multiple such pairs, we should further find the one with the maximum *x*, which must be unique. After obtaining the optimal (*x*, *y*), the minimum integer have a form of 444...777..77.

At first, we find out all the lucky integers and sort them in an increasing order. These lucky numbers in fact have divided the interval [1, 1*E* + 9] into several sub-intervals, whose borders are just these lucky numbers. Suppose that we have *m* intervals [*a*_{0}, *a*_{1}], [*a*_{1}, *a*_{2}], ..., [*a*_{m - 1}, *a*_{m}], where *a*_{0} = 1, *a*_{1} = 4, *a*_{2} = 7, *a*_{3} = 44, ...*a*_{m} = 1*E* + 9. For any interval [*x*, *y*] that contains exactly *k* lucky numbers, we must have and . Therefore, it suffices to count the number of pairs (*x*, *y*) that satisfy the above condition. Equivalently, we can enumerate all the feasible intervals, i.e., [*a*_{i}, *a*_{i + 1}] and [*a*_{i + k}, *a*_{i + k + 1}], and find out the number of common integers that also appear in [*p*_{l}, *p*_{r}] and [*v*_{l}, *v*_{r}].

Moreover, one should take care of one tricky case, i.e., *k* = 1. As one can see, when *k* = 1, [*a*_{i}, *a*_{i + 1}] and [*a*_{i + k}, *a*_{i + k + 1}] have a common integer *a*_{i + 1}, which implies that *a*_{i + 1} has been counted twice if it belongs to both [*p*_{l}, *p*_{r}] and [*v*_{l}, *v*_{r}]. Therefore, one should decrease the counting result by one if this case occurs.

As this is a tree, deleting any edges will divide it into several independent smaller trees. We can first delete all the edges that have a weight of lucky number and then adopt “union and find” to construct the smaller connected components.

We use *a*_{i} to denote the number of nodes belonging to the *i*-th component. Now, instead of counting the required answer, we count the number of triples that do not satisfy the requirements. Note that if we pick all the three nodes from the *i*-th component, they definitely are against the requirements. This case gives , where all *a*_{i} ≥ 3. Next, if we pick two nodes from the *i*-th component while one node from another different component, this gives , where *a*_{i} ≥ 2. Finally, the desired result is *n*(*n* - 1)(*n* - 2) - *n*_{1} - *n*_{2}.

If the given sequence is not initially non-decreasing, we need at least one lucky number.

We denote the original sequence and the sorted sequence as *a* and *b*, respectively. For each element in *a*, it appears in *b* at a unique position. There are exactly *n* such pairs, and thus we can adopt two arrays to record their relationship. We use *atob*[*i*] to denote that the *i*-th element in *a* is at position *atob*[*i*] in *b*, while using *btoa*[*i*] to denote that the *i*-th element in *b* is at position *btoa*[*i*] in *a*. Then, we enumerate each element in array *b*, and try to move the “required” element to the current position.

If *i* = *btoa*[*i*], it is not necessary to move any element. On the contrary, we should move the *btoa*[*i*]-th element to the *i*-th position. If either one of *a*[*i*] or *a*[*btoa*[*i*]] is a lucky number, it takes one “move” to exchange their positions. Otherwise, we can first exchange *a*[*i*] with a lucky number at position *j*, and then move *a*[*btoa*[*i*]] to the *i*-th position, which costs two “moves”.

From the above operations, one can check that it is always feasible to sort the original array in a non-decreasing order within 2*n* “moves as long as there is at least one lucky number. Note that whenever we exchange two elements, both *atob* and *btoa* should be updated at the same time.