====== Up and Down ======

===== 풀이 =====
  * [[ps:problems:boj:11054]] 과 같은 문제인데, 증가하는 구간과 감소하는 구간이 반드시 둘다 존재해야 한다는 점만 다르다. 기본 풀이는 [[ps:problems:boj:11054]] 를 참고하고, 여기에 증가하는 구간과 감소하는 구간이 존재하도록 확인하는 조건문만 추가해주면 된다
  * 시간복잡도는 O(nlogn)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 32683. Up and Down".

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

Tags: [lis]
"""

import sys
from teflib import psutils
from teflib import seqtask


@psutils.run_n_times
def main():
    _N = int(sys.stdin.readline())
    a = [int(x) for x in sys.stdin.readline().split()]

    lis_lengths = seqtask.longest_inc_subseq_length_by_last_elem(a)
    lds_lengths = seqtask.longest_dec_subseq_length_by_first_elem(a)
    answer = 0
    for lis_len, lds_len in zip(lis_lengths, lds_lengths):
        if lis_len > 1 and lds_len > 1:
            answer = max(answer, lis_len + lds_len - 1)

    print(answer)


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:골드_1}}