====== DP (Large) ======

===== 풀이 =====
  * A[i]를 포함하는 LIS의 길이를 구하라는 문제.
  * 이것은 A[i]로 끝나는 LIS와 A[i]로 시작하는 LIS를 합쳐놓은 것이 된다.
  * 모든 i에 대해서 [[ps:tutorial:lis#a_i_로_끝나는_or_시작하는_lis_or_lds_의_길이|A[i]로 끝나는 LIS와 A[i]로 시작하는 LIS]]를 O(nlogn)에 구해두면, 각 쿼리를 O(1)에 처리할수 있다
  * 총 시간복잡도는 O(nlogn + q)

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

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

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:플래티넘_5}}