409032: GYM103422 B Gorbachev Sort

O(N) Sort

In light of these groundbreaking discoveries, Mikhail Gorbachev decides he must do something similar to be remembered in the history books. The first thing he noticed was that he had to improve conditions in the Union. Initially, each man is given a job, and this is described for person $$$i$$$ by the difficulty of his job $$$v[i]$$$. In short, he wants every person on the social ladder to have a job that suits him, not something overly demanding. So he defines his sorting procedure like this:

void gorbasort(vector<int>& v) {
  int i;
  for(i=v.size()-2; i>=0; i=i-1) {
    v[i]=min(v[i],v[i+1]);
  }
}

However, this procedure is bound to worsen the state of the current economy, due to the fact that not as many resources are produced (research for atomic bombs, weapons, etc.) as were produced before the sorting. Thus, because Gorbachev wants to use his formula, giving a string of numbers to represent how difficult the job is for each man, determine the subsequence with the maximum amount after applying gorbasort on it.

In the first line of input there is $$$N$$$ ($$$1 \le N \le 10^5$$$). Then, $$$N$$$ numbers follow, the i-th descibing $$$v[i]$$$ ($$$1 \le v[i] \le 10^9$$$).

Let $$$X$$$, $$$Y$$$ and $$$Sum$$$ be displayed, where $$$X$$$ and $$$Y$$$ are the indices that border the subsequence requested in the query, and $$$Sum$$$ is the sum of the elements in that subsequence after applying $$$gorbasort$$$ on this substring.

7
4 2 5 15 6 7 2

1 6 28

• $$$1 \le v[i] \le 1\,000\,000\,000$$$
• $$$1 \le N \le 100\,000$$$