====== 가장 긴 바이토닉 부분 수열 ======

===== 풀이 =====
  * 바이토닉 부분 수열에서 가장 큰 수를 S[i] 로 고정시킨다면, 가장 긴 바이토닉 부분 수열은, S[i]로 끝나는 LIS와 S[i]로 시작하는 LDS를 합쳐놓은 것이 된다.
  * 모든 i에 대해서 [[ps:tutorial:lis#a_i_로_끝나는_or_시작하는_lis_or_lds_의_길이|S[i]로 끝나는 LIS와 S[i]로 시작하는 LDS]]를 O(nlogn)에 구해둔 뒤에, 가장 큰 수가 S[i]인 가장 긴 바이토닉 부분 수열들 중에서 가장 긴 것을 O(n)에 찾으면 된다.
  * 총 시간복잡도는 O(nlogn)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11054. 가장 긴 바이토닉 부분 수열".

- Problem link: https://www.acmicpc.net/problem/11054
- Solution link: http://www.teferi.net/ps/problems/boj/11054

Tags: [LIS]
"""

from teflib import seqtask


def main():
    _N = int(input())
    A = [int(x) for x in input().split()]

    lis_lengths = seqtask.longest_inc_subseq_length_by_last_elem(A)
    lds_lengths = seqtask.longest_dec_subseq_length_by_first_elem(A)
    print(max(l1 + l2 for l1, l2 in zip(lis_lengths, lds_lengths)) - 1)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency
    * [[:ps:teflib:seqtask#longest_inc_subseq_length_by_last_elem|teflib.seqtask.longest_inc_subseq_length_by_last_elem]]
    * [[:ps:teflib:seqtask#longest_dec_subseq_length_by_first_elem|teflib.seqtask.longest_dec_subseq_length_by_first_elem]]

{{tag>BOJ ps:problems:boj:골드_4}}