The Ingredients of Gourmet Dining: Cuisine, Timing, Company. And...

Juri

I hope you are well. Haruna here. It has already been a week since our New Year’s adventure.

To summarize last week’s events, our New Year’s commotion was a tale of the Gourmet Research Society taking on the giant food distributor Nyao Foods, driven solely by our passion for delicious food, to protect the little restaurant Sparrow from closure. When Nyao Foods sought to acquire it and turn it into a chain restaurant, we accepted a cooking contest with the restaurant’s fate at stake. Even the Gourmet Helmet Gang became involved, turning an entire corner of the city upside down. In the end, after our showdown, Sparrow survived with its character intact. And today, we have gained a wonderful new goal: to find more hidden gems like it and share them with the world.

Our Gourmet Research Society has carefully selected $N$ restaurants. We have noted that the $i$-th restaurant has a deliciousness value of $A_i$. We are planning a tour that visits restaurants $1$ through $N$ in order. If a restaurant does not meet our standards... we intend to blow it up beforehand. We may choose several of the $N$ restaurants to blow up, then close the gaps while preserving the order of the remaining restaurants. Oh, a tour without eating would be unthinkable, so we must leave at least two restaurants intact. As we visit the remaining restaurants in order, we will consider whether the food becomes more delicious along the way.

Incidentally, the Prefect Team may be guarding some restaurants... Fortunately, we have already obtained that information. If $S_i=\texttt{0}$, we may blow up restaurant $i$. If $S_i=\texttt{1}$, however, I am afraid we cannot blow it up. We would not want to spoil our special gourmet tour, after all. Heehee.

For each pair of consecutively visited restaurants, if the next restaurant is more delicious than the previous one, our spirits will rise by the difference in their deliciousness. Conversely, if it is less delicious, our spirits will fall by that amount. Let us call the sum of all these signed differences in deliciousness between adjacent restaurants throughout the tour our satisfaction. I wonder what the maximum satisfaction we can achieve is. Still, we would like to enjoy as much variety as possible, so among tours with maximum satisfaction, we would like to minimize the number of restaurants blown up.

To define satisfaction precisely... suppose $M$ restaurants remain, and the $i$-th of them has deliciousness $B_i$. Then satisfaction is

as you see.

Now, Sensei. Let us find the maximum satisfaction and the minimum number of restaurants we must blow up to achieve it.

The sum of $N$ over all test cases does not exceed $200\,000$.

Time limit

1000 ms

Memory limit

1024 MB

Checker

CUSTOM