407682: GYM102873 B Rabbit Game

John the farmer has two rabbits, which like to keep eating bigger and bigger carrots. He likes setting up interesting games for them. One day he has set up the following game:

There are $$$n$$$ carrots in a row, carrot $$$i$$$ has size $$$a_i$$$. The two rabbits start the game at different endpoints. Each rabbit first eats the carrot at that endpoint and then keeps moving to every next carrot as long as such a next carrot is greater than or equal to the previous carrot.

So, the first rabbit first eats the first carrot, then second, third, and so on, as long as every next carrot is not-smaller than the previous one. Similarly, the other rabbit starts from the last carrot and then moves to the second last carrot, and so on.

If rabbits meet at some position, one of them eats the carrot there and they both stop. A carrot can't be eaten twice, and a rabbit can't skip a carrot. It doesn't matter which rabbit moves first at the beginning or at any moment.

John is wondering how many carrots can the rabbits eat at most. Can you help him find the answer to his question?

The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$ denoting the number of carrots.

The second line contains $$$n$$$ space-separated integers $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$ denoting the size of each carrot.

Print one integer — the maximum possible number of eaten carrots.

4
1 2 3 4

4

5
1 3 2 3 1

4

9
1 1 2 1 9 2 1 1 2

4

7
1 3 5 4 4 3 2

7

5
2 2 2 2 2

5

In the first sample, it is easy to see that the rabbits can eat all carrots. A possible way the game could go is the following: the first rabbit eats carrot $$$1$$$ (starting carrot) –> the second rabbit eats carrot $$$4$$$ (starting carrot) –> the first rabbit eats carrot $$$2$$$ ($$$2$$$ > $$$1$$$) –> the first rabbit eats carrot $$$3$$$ ($$$3$$$ > $$$2$$$). Keep in mind that the second rabbit can not eat carrot $$$3$$$ because it is smaller than the current carrot that rabbit $$$2$$$ ate.

In the third sample, the rabbits can eat at most $$$4$$$ carrots. The possible actions of the game are the following: The first rabbit eats the first carrot, then he moves to the second one because its size is equal to the current carrot. Then he eats the third carrot because it is greater than the current carrot (which is now carrot $$$2$$$). He stops here because the fourth carrot is smaller than the current one. The second rabbit can only eat the starting carrot (because the next carrot is smaller than it) and the game ends because no rabbit can eat any more carrots.