====== DP (Small) ======

===== 풀이 =====
  * [[ps:problems:boj:31503]]의 쉬운 버전. 풀이는 링크 참고. 코드도 동일하다.
  * 제한이 작아서, O(n^2)에 LIS를 구해도 풀리기는 하다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 31501. DP (Small)".

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

Tags: [lis]
"""

import sys
from teflib import seqtask


def main():
    _N, Q = [int(x) for x in sys.stdin.readline().split()]
    D = [int(x) for x in sys.stdin.readline().split()]

    len_by_last = seqtask.longest_inc_subseq_length_by_last_elem(D)
    len_by_first = seqtask.longest_inc_subseq_length_by_first_elem(D)

    for _ in range(Q):
        A = int(sys.stdin.readline()) - 1
        print(len_by_last[A] + len_by_first[A] - 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_inc_subseq_length_by_first_elem|teflib.seqtask.longest_inc_subseq_length_by_first_elem]]

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