Disturbing Distribution

Observation 1: multiplying numbers $>1$ together is usually a scam

Take any valid removed subsequence, and ignore all the $1$'s inside it for a moment. Suppose the remaining numbers are

$$b_1,b_2,\dots,b_m \quad (b_i \ge 2).$$

Its cost is

$$\prod_{i=1}^m b_i.$$

Now compare that with deleting those $b_i$ separately, which would cost

$$\sum_{i=1}^m b_i.$$

For two numbers $x,y \ge 2$,

$$xy \ge x+y,$$

with equality only for $x=y=2$.

So if you repeatedly “merge” numbers in a chain, the sum never decreases. That means for any chain containing numbers $\ge 2$,

$$\prod_{i=1}^m b_i \ge \sum_{i=1}^m b_i.$$

So putting several numbers bigger than $1$ into the same subsequence is never better than paying for them separately. At best, for $2,2$, it ties. That’s it. No black magic here.

---

Observation 2: $1$'s are special little goblins

A $1$ does not change a product:

$$1 \cdot x = x.$$

So if a subsequence looks like

$$[1,1,\dots,1,x], \quad x>1,$$

it costs just

$$x.$$

Also, a subsequence consisting only of $1$'s costs exactly

$$1.$$

No matter how many $1$'s you pack into it.

So the entire problem becomes:

• every value $>1$ contributes at least its own value,
• and the only extra cost can come from some leftover subsequence made only of $1$'s.

---

Lower bound

Let’s prove a clean lower bound.

Every chain that contains at least one number $>1$ costs at least the sum of those numbers in that chain. Summing over all such chains gives at least

$$\sum_{i:a_i>1} a_i.$$

What about chains made only of $1$'s? Each such chain costs $1$.

Now notice the crucial thing:

• if the array ends with $1$, then the final suffix of $1$'s cannot be attached to any chain containing a number $>1$,
• because in a nondecreasing subsequence, once you take a number $>1$, you cannot later take a $1$.

So if $a_n=1$, at least one all-$1$ chain is unavoidable. Hence

$$\text{answer} \ge \sum_{i:a_i>1} a_i + 1.$$

If $a_n>1$, such a forced leftover block does not exist, so we only get

$$\text{answer} \ge \sum_{i:a_i>1} a_i.$$

Together,

$$\text{answer} \ge \sum_{i:a_i>1} a_i + [a_n=1].$$

---

Upper bound / construction

Now we show this bound is achievable.

Look at every maximal block of $1$'s.

• If the block has some later element $>1$, attach the whole block to the next such element. That forms a valid nondecreasing subsequence like $$[1,1,\dots,1,x],$$ whose cost is just $x$.
• Any element $>1$ not used this way is removed alone.
• If the array ends with a block of $1$'s, remove that block alone with cost $1$.

This gives total cost exactly

$$\sum_{i:a_i>1} a_i + [a_n=1].$$

So the lower bound is tight.

---

Final formula

The minimum total cost is

$$\boxed{\sum_{i:a_i>1} a_i + [a_n=1]}$$

where $[a_n=1]$ is $1$ if the last element is $1$, and $0$ otherwise.

The modulus $676{,}767{,}677$ is basically decorative here, because the answer is tiny anyway. But sure, we can still mod it.

---

Complexity

We just scan the array once.

For each test case:

$$O(n)$$

With the given constraints, this is hilariously safe.