oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

pokeclone Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

pokeclone.html

PokéTrainer Little Joseph is very good in Biology and wants to clone Mew. Suddenly, something has happened! An evil super-Mankey randomly appeared in front of him and passed him the DNA of Mew. Excited at the new opportunity, Little Joseph began studying Mew's DNA in his secret lab (and can only be accessed if you have all 9 pieces of the Secret Laboratory Map).

Little Joseph found out that Pokémon DNA is not made of A, C, T and G but rather made out of a sequence of integers. He also found out that Mew's DNA are made out of "coding integers" and "non-coding integers", which means that only certain integers in the DNA sequence are used by the body.

The rest of the non-coding regions will actually form miRNA which is a dsRNA which will be brought by Dicer to the RNA-Induced Silencing Complex for controlling gene expression. But you don't need to know that.

Little Joseph found out that there is a coding sequence that is a subsequence of the DNA sequence. However, it need not be continuous in the DNA sequence, meaning that a DNA sequence of 1 7 2 5 can have a coding sequence of 1 7 5 (even though this sequence is not continuous in the DNA).

Little Joseph also found out that the coding sequence is always of odd length N, with the first (N+1)/2 integers of the sequence making a strictly increasing sequence and the last (N+1)/2 integers of the sequence making a strictly decreasing sequence.

For example, 1 2 3 4 3 2 0 is a coding sequence but both 1 2 3 4 3 2 2 and 1 2 3 4 5 3 1 is not.

These conditions will allow for many coding sequence, but the coding sequence that Little Joseph needs is always the longest possible coding sequence.

Your task as a PokéProgrammer is to find the length of the longest coding sequence.

Input

The first line of input contains an integer N (1 ≤ N ≤ 15,000) representing the number of integers in Mew's DNA sequence. The next line contains N integers representing Mew's DNA sequence.

Output

Print out the length of the longest coding sequence on a single line.

Sample Input 1

11
1 2 3 4 5 1 4 3 2 1 10

Sample Output 1

9

Explanation for Sample Output 1

This is gotten from the coding sequence of 1 2 3 4 5 4 3 2 1.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110051s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o pokeclone -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.