Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.Arrays;
- import java.util.InputMismatchException;
- /**
- * Created by sijhanwa on 9/21/14.
- */
- public class D2 {
- private static int getCiel(int a[],int val,int l, int r){
- int m = 0;
- while (l<r-1){
- m = l+(r-l)/2;
- if(a[m]>val){
- r = m;
- }else{
- l=m;
- }
- }
- return r;
- }
- private static int getLIS(int[] a, int startIndex,int N) {
- int length = 1;
- int [] lists = new int[a.length-1];
- lists[0] = a[startIndex];
- for (int i = 1;i<N;i++){
- if(a[i+startIndex]<lists[0]){
- lists[0]=a[i+startIndex];
- }
- else if(a[i+startIndex]>lists[length-1]){
- lists[length++]=a[i+startIndex];
- }
- else{
- lists[getCiel(lists,a[i+startIndex],0,length-1)] = a[i+startIndex];
- }
- }
- return length;
- }
- public static void main(String[] args) throws IOException {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- PrintWriter pw = new PrintWriter(System.out);
- InputReader in = new InputReader(System.in);
- int TC = in.readInt();
- while (TC-- > 0) {
- int N = in.readInt();
- int [] numbers = new int[2*N+1];
- for(int i = 0;i<N;i++){
- numbers[i] = in.readInt();
- numbers[i+N] = numbers[i];
- }
- int max = 0;
- for(int i = 0;i<N;i++){
- max = max(max,getLIS(numbers,i,N));
- }
- pw.println(max);
- }
- pw.flush();
- pw.close();
- }
- private static int max(int n1, int n2) {
- return (n1>n2?n1:n2);
- }
- private static int min(int n1, int n2) {
- return (n1<n2?n1:n2);
- }
- }
- /*
- //initialize
- InputReader in = new InputReader(System.in);
- OutputWriter out = new OutputWriter(System.out);
- //read int
- int i = in.readInt();
- //read string
- String s = in.readString();
- //read int array of size N
- int[] x = IOUtils.readIntArray(in,N);
- //printline
- out.printLine("X");
- //flush output
- out.flush();
- //remember to close the
- //outputstream, at the end
- out.close();
- */
- class InputReader {
- private InputStream stream;
- private byte[] buf = new byte[1024];
- private int curChar;
- private int numChars;
- private SpaceCharFilter filter;
- public InputReader(InputStream stream) {
- this.stream = stream;
- }
- public int read() {
- if (numChars == -1)
- throw new InputMismatchException();
- if (curChar >= numChars) {
- curChar = 0;
- try {
- numChars = stream.read(buf);
- } catch (IOException e) {
- throw new InputMismatchException();
- }
- if (numChars <= 0)
- return -1;
- }
- return buf[curChar++];
- }
- public int readInt() {
- int c = read();
- while (isSpaceChar(c))
- c = read();
- int sgn = 1;
- if (c == '-') {
- sgn = -1;
- c = read();
- }
- int res = 0;
- do {
- if (c < '0' || c > '9')
- throw new InputMismatchException();
- res *= 10;
- res += c - '0';
- c = read();
- } while (!isSpaceChar(c));
- return res * sgn;
- }
- public String readString() {
- int c = read();
- while (isSpaceChar(c))
- c = read();
- StringBuilder res = new StringBuilder();
- do {
- res.appendCodePoint(c);
- c = read();
- } while (!isSpaceChar(c));
- return res.toString();
- }
- public boolean isSpaceChar(int c) {
- if (filter != null)
- return filter.isSpaceChar(c);
- return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
- }
- public String next() {
- return readString();
- }
- public interface SpaceCharFilter {
- public boolean isSpaceChar(int ch);
- }
- }
- class OutputWriter {
- private final PrintWriter writer;
- public OutputWriter(OutputStream outputStream) {
- writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
- }
- public OutputWriter(Writer writer) {
- this.writer = new PrintWriter(writer);
- }
- public void print(Object...objects) {
- for (int i = 0; i < objects.length; i++) {
- if (i != 0)
- writer.print(' ');
- writer.print(objects[i]);
- }
- }
- public void printLine(Object...objects) {
- print(objects);
- writer.println();
- }
- public void close() {
- writer.close();
- }
- public void flush() {
- writer.flush();
- }
- }
- class IOUtils {
- public static int[] readIntArray(InputReader in, int size) {
- int[] array = new int[size];
- for (int i = 0; i < size; i++)
- array[i] = in.readInt();
- return array;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement