You are given an array $$$a$$$ of $$$n$$$ integers. A subsequence of $$$a$$$ can be obtained by keeping some (perhaps none, or all) elements of $$$a$$$, in the same order as in the original array. Formally, a subsequence $$$b$$$ of length $$$k$$$ can consist of $$$a[i_1],a[i_2] \ldots, a[i_k]$$$, if and only if $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$$$.
For example, if $$$a=[1,2,5,4,3]$$$, then $$$[$$$ $$$]$$$, $$$[1]$$$, or $$$[1,5,4]$$$ are subsequences of $$$a$$$, while $$$[6]$$$, $$$[1,1]$$$ or $$$[3,4,5]$$$ are not.
Unfortunately, not all subsequences are created equal, some being fancier than others. These fancy subsequences are also known as constant subsequences. A subsequence $$$b=$$$ $$$[$$$ $$$a[i_1],a[i_2],\ldots , a[i_k]$$$ $$$]$$$ is considered constant if $$$b[1]+1=b[2]+2= \ldots = b[k]+k$$$.
Find the maximum length $$$k$$$ of any constant subsequence of $$$a$$$, as well as the indices $$$i_1, i_2, \ldots, i_k$$$ coresponding to any maximal constant subsequence.
If there are multiple constant subsequences of length $$$k$$$, you may print any.
The first line of input contains one integer $$$n$$$ ($$$1 \le n \le 10^6$$$) - the length of array $$$a$$$. The second line of input contains $$$n$$$ integers, the elements of array $$$a$$$ ($$$1 \le a_1, a_2, \ldots, a_n \le n$$$).
Print the maximum length $$$k$$$ of any constant subsequence, followed by $$$k$$$ indices $$$i_1, i_2, \ldots, i_k$$$ coresponding to the elements of $$$a$$$ present in some constant subsequence of length $$$k$$$.
If there are multiple constant subsequences of length $$$k$$$, you may print any.
7 5 6 1 4 2 3 2
4 1 4 6 7
The answer for the sample is $$$[a_1,a_4,a_6,a_7]=[5,4,3,2]$$$. $$$[5,4,3,2]$$$ is constant, since $$$5+1=4+2=3+3=2+4$$$.
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
You are a very generous man. One day you decided to make a trip across the city. There were many homeless man who were begging for money. The city can be encoded by an array $$$A$$$ of $$$N$$$ elements , each element being a different place. If the value at $$$A_i$$$ is positive ( including 0 ) , it means that you can steal withdraw $$$A_i$$$ dollars. If it is negative then there is some homeless man begging for $$$|A_i|$$$ dollars. As you are a generous man , you will help exactly $$$K$$$ homeless men. You will visit the $$$N$$$ places in order.Knowing that you initially have 0 dollars and can help a homeless man if and only if you have enough money when you visit him , which is the maximum amount of money you can have after helping $$$K$$$ homeless men of your choosing.
The input consists of integers $$$N,K$$$ , followed by vector $$$A$$$ of $$$N$$$ elements , describing each place in the city.
Print one number - The maximum amount of money you can have after helping $$$K$$$ homeless men. Print -1 if you cannot help $$$K$$$ homeless men.
5 2 1 -3 100 -50 -51
0
Initially we have 0 dollars. We need to help 2 homeless men. We cannot help the one begging for 3 dollars , since we can have at most 1 dollar when we visit him. Instead we will be able to help the last 2 homeless men , since they beg for $$$|-51|+|-50| = 101$$$ dollars , which is the exact amount of money we have when we visit them.