암호화 알고리즘의 약점
시간 제한2초메모리 제한128 MB
수열에서 p<q<r<s를 만족하며 특정 값 대소 패턴을 이루는 네 인덱스가 존재하는지, n이 5000까지인 상황에서 효율적으로 판별하는 문제입니다.
문제
수열 A[1], A[2], ..., A[n]을 암호화한다고 하자. 어떤 암호화 알고리즘은 특정한 형태의 부분 수열이 존재할 때 복호화 결과가 유일하지 않다는 약점을 가진다.
주어진 수열이 이 약점을 가지는지 판별하시오.
서로 다른 네 인덱스 p, q, r, s가 1 <= p < q < r < s <= n을 만족한다고 하자. 이때 다음 두 조건 중 하나가 성립하면 수열은 약점을 가진다.
A[q] < A[s] < A[p] < A[r]A[q] > A[s] > A[p] > A[r]
입력
첫째 줄에 데이터의 개수 T가 주어진다. 1 <= T <= 10이다.
각 데이터는 두 줄로 이루어진다. 첫째 줄에는 수열의 길이 n이 주어진다. 4 <= n <= 5,000이다. 둘째 줄에는 A[1], A[2], ..., A[n]이 순서대로 주어진다.
각 A[i]는 1 이상 10,000 이하이며, 한 데이터 안의 모든 A[i]는 서로 다르다.
출력
각 데이터마다 한 줄에 결과를 출력한다. 수열이 약점을 가지면 Yes, 그렇지 않으면 No를 출력한다.