/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
空の列 X と空のスタック S があります。また、項数が N の整数列 A=(a_1,\ldots,a_N) が与えられます。
高橋君は i=1,\ldots,N の順に、以下の 2 つの操作のうち一方を行います。
- A の先頭の整数 a_i を S の先頭に移動させる。
- A の先頭の整数 a_i を捨てる。
また、高橋君は S が空でない任意のタイミングで次の操作をすることが出来ます。
- S の先頭の整数を X の末尾に移動させる。
最終的な X に対し、スコアを以下のように定めます。
- X が広義単調増加な場合、すなわち X=(x_1,\ldots,x_{|X|}) とした時に任意の整数 i(1 \leq i \lt |X|) に対して x_i \leq x_{i+1} が成り立つ場合、スコアは |X| である。(|X| は X の項数)
- X が広義単調増加でない場合、スコアは 0 である。
スコアの最大値を求めてください。
制約
- 1 \leq N \leq 50
- 1 \leq a_i \leq 50
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N
出力
答えを出力せよ。
入力例 1
7 1 2 3 4 1 2 3
出力例 1
5
以下のように操作をすると最終的な X が (1,1,2,3,4) となり、スコアが 5 になります。
- a_1=1 を S の先頭に移動させる。
- S の先頭の 1 を X の末尾に移動させる。
- a_2=2 を S の先頭に移動させる。
- a_3=3 を捨てる。
- a_4=4 を S の先頭に移動させる。
- a_5=1 を S の先頭に移動させる。
- S の先頭の 1 を X の末尾に移動させる。
- a_6=2 を S の先頭に移動させる。
- S の先頭の 2 を X の末尾に移動させる。
- a_7=3 を S の先頭に移動させる。
- S の先頭の 3 を X の末尾に移動させる。
- S の先頭の 4 を X の末尾に移動させる。
また、スコアを 6 以上にすることは出来ません。よってスコアの最大値は 5 です。
入力例 2
10 1 1 1 1 1 1 1 1 1 1
出力例 2
10
Score : 600 points
Problem Statement
There is an empty sequence X and an empty stack S. Also, you are given an integer sequence A=(a_1,\ldots,a_N) of length N.
For each i=1,\ldots,N in this order, Takahashi will do one of the following operations:
- Move the integer a_i onto the top of S.
- Discard the integer a_i from A.
Additionally, Takahashi may do the following operation whenever S is not empty:
- Move the integer at the top of S to the tail of X.
The score of the final X is defined as follows.
- If X is non-decreasing, i.e. if x_i \leq x_{i+1} holds for all integer i(1 \leq i \lt |X|), where X=(x_1,\ldots,x_{|X|}), then the score is |X| (where |X| denotes the number of terms in X).
- If X is not non-decreasing, then the score is 0.
Find the maximum possible score.
Constraints
- 1 \leq N \leq 50
- 1 \leq a_i \leq 50
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 \ldots a_N
Output
Print the answer.
Sample Input 1
7 1 2 3 4 1 2 3
Sample Output 1
5
The following operations make the final X equal (1,1,2,3,4), for a score of 5.
- Move a_1=1 onto the top of S.
- Move 1 at the top of S to the tail of X.
- Move a_2=2 onto the top of S.
- Discard a_3=3.
- Move a_4=4 onto the top of S.
- Move a_5=1 onto the top of S.
- Move 1 at the top of S to the tail of X.
- Move a_6=2 onto the top of S.
- Move 2 at the top of S to the tail of X.
- Move a_7=3 onto the top of S.
- Move 3 at the top of S to the tail of X.
- Move 4 at the top of S to the tail of X.
We cannot make the score 6 or greater, so the maximum possible score is 5.
Sample Input 2
10 1 1 1 1 1 1 1 1 1 1
Sample Output 2
10