import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class BaitapTuan5 {
	static Scanner inp = new Scanner(System.in);
	public static void INPUT(ArrayList<Integer> arrInt) {
		System.out.println("Nhap day so nguyen ");
		String str = inp.nextLine();
		String strInt[] = str.split(" ");
		for (int i=0;i<strInt.length;i++) arrInt.add(Integer.parseInt(strInt[i]));
	}
	public static void OUTPUT(ArrayList<Integer> arrInt) {
		System.out.println(arrInt.toString());
	}
	public static void ADD(ArrayList<Integer> arrInt) {
		System.out.println("Nhap gia tri can them: ");
		int gt = inp.nextInt();
		int vt = 0;
		while (vt < arrInt.size() && gt>arrInt.get(vt)) vt++;
		if (vt>=arrInt.size()-1) arrInt.add(gt);
		else arrInt.add(vt, gt);
	}
	static int brinarySeach(ArrayList<Integer> arrInt,int giatricantim ) {
		int l=0;
		int r=arrInt.size()-1;
		for(int i=l;i<=r;i++) {
			int mid=(l+r)/2;
			if(arrInt.get(mid)==giatricantim) {
				return mid;
			}else if(giatricantim>arrInt.get(mid)) {
				l=mid+1;
			}else {
				r=mid-1;
			}
		}
		return -1;
	}
	static void DELETE(ArrayList<Integer> arrInt , int gt) {
		if(brinarySeach(arrInt , gt) == -1) {
			System.out.println("khong co gia tri can xoa trong mang ");
		}else {
			arrInt.remove(brinarySeach(arrInt , gt));
			System.out.println("da xoa gia tri can xoa");
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList<Integer> arrInt = new ArrayList<Integer>();
				int menu = 1;
		while (menu!=0 ) {
			System.out.println("Select menu: 1|INPUT 2|OUTPUT 3|SORT 4|ADD 5|SEARCH 0|thoat");
			menu = inp.nextInt();
			inp.nextLine();
			switch (menu) {
				case 1: { INPUT(arrInt);break;}
				case 2: { OUTPUT(arrInt);break;}
				case 3: { Collections.sort(arrInt);break;}
				case 4: { ADD(arrInt);break;}
				case 5: { 
					System.out.println("Nhap gia tri tim kiem ");
					int gt=inp.nextInt();
					int result = brinarySeach(arrInt, gt);
					if (result == -1) System.out.println("Khong tim thay");
					else System.out.println("Tim thay tai vi tri "+result);
					break;
				}
				case 6:{
					int gt;
					System.out.println("nhap gia tri can xoa ");
					gt = inp.nextInt();
					DELETE(arrInt, gt);
					break;
				}
			}
		}
		
		
		
	}

}