1121_B. Mike and Children_16216
Mike decided to teach programming to children in an elementary school. He knows that it is not an easy task to interest children in that age to code. That is why he decided to give each child two sweets.

Mike has n sweets with sizes a_1, a_2, …, a_n. All his sweets have different sizes. That is, there is no such pair (i, j) (1 ≤ i, j ≤ n) such that i ≠ j and a_i = a_j.

Since Mike has taught for many years, he knows that if he gives two sweets with sizes a_i and a_j to one child and a_k and a_p to another, where (a_i + a_j) ≠ (a_k + a_p), then a child who has a smaller sum of sizes will be upset. That is, if there are two children who have different sums of sweets, then one of them will be upset. Apparently, Mike does not want somebody to be upset. 

Mike wants to invite children giving each of them two sweets. Obviously, he can't give one sweet to two or more children. His goal is to invite as many children as he can. 

Since Mike is busy preparing to his first lecture in the elementary school, he is asking you to find the maximum number of children he can invite giving each of them two sweets in such way that nobody will be upset.

Input

The first line contains one integer n (2 ≤ n ≤ 1 000) — the number of sweets Mike has.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^5) — the sizes of the sweets. It is guaranteed that all integers are distinct.

Output

Print one integer — the maximum number of children Mike can invite giving each of them two sweets in such way that nobody will be upset.

Examples

Input


8
1 8 3 11 4 9 2 7


Output


3


Input


7
3 1 7 11 9 2 12


Output


2

Note

In the first example, Mike can give 9+2=11 to one child, 8+3=11 to another one, and 7+4=11 to the third child. Therefore, Mike can invite three children. Note that it is not the only solution.

In the second example, Mike can give 3+9=12 to one child and 1+11 to another one. Therefore, Mike can invite two children. Note that it is not the only solution.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
//import java.lang.Math;

public class Exercise {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            arr.add(input.nextInt());
        }
        int[] counter = new int[200000];
        for (int i : counter) i = 0;

        for (int i = 0; i < n; i++ ){
            for (int j = i + 1; j < n; j++){
                counter[arr.get(i) + arr.get(j)] += 1;
            }
        }
        int max = 0;
        for (int i : counter) {
            if (i > max) max = i;
        }
        System.out.println(max);
        // A - техно кубок

//        Scanner input = new Scanner(System.in);
//        int n = input.nextInt();
//        //int m = input.nextInt();
//        int k = input.nextInt();
//        ArrayList<Integer> forces = new ArrayList<>();
//        for (int i = 0; i < n; ++i) {
//            forces.add(input.nextInt());
//        }
//        ArrayList<Integer> schools = new ArrayList<>();
//        for (int i = 0; i < n; ++i) {
//            schools.add(input.nextInt());
//        }
//        ArrayList<Integer> pupils = new ArrayList<>();
//        for (int i = 0; i < k; ++i) {
//            pupils.add(input.nextInt());
//        }
//        int counter = 0;
//        for (int i : pupils) {
//            for (int j = 0; j < n; ++j) {
//                if (schools.get(j) == schools.get(i - 1) && forces.get(j) > forces.get(i - 1)) {
//                    counter++;
//                    break;
//                }
//            }
//        }
//        System.out.println(counter);

        // А - покупка воды

//        Scanner input = new Scanner(System.in);
//        int q = input.nextInt();
//        ArrayList<Long> sums = new ArrayList<>();
//        for (int i = 0; i < q; ++i) {
//            long sum;
//            long n = input.nextLong();
//            int a = input.nextInt();
//            int b = input.nextInt();
//            if (b / 2 < a) {
//                sum = (n - (n % 2)) / 2 * b + (n % 2) * a;
//            } else {
//                sum = n * a;
//            }
//            sums.add(sum);
//        }
//        for (long i : sums) {
//            System.out.println(i);
//        }


        // B - эмоции

//        Scanner input = new Scanner(System.in);
//        int n = input.nextInt();
//        int m = input.nextInt();
//        int k = input.nextInt();
//        ArrayList<Integer> arr = new ArrayList<>();
//        for (int i = 0; i < n; ++i) {
//            arr.add(input.nextInt());
//        }
//        Collections.sort(arr);
//        long happiness;
//        long max = arr.get(arr.size() - 1);
//        long premax = arr.get(arr.size() - 2);
//        happiness = m / (k + 1) * (k * max + premax) + (m % (k + 1)) * max;
//        System.out.println(happiness);

        // А - лучший подотрезок

//        Scanner input = new Scanner(System.in);
//        int n = input.nextInt();
//        ArrayList<Integer> arr = new ArrayList<>();
//        for (int i = 0; i < n; ++i) {
//            arr.add(input.nextInt());
//        }
//        int maxEl = -1;
//        for (int i : arr) {
//            if (i > maxEl) maxEl = i;
//        }
//        int max = 1;
//        int j;
//        for (int i = 0; i < arr.size(); i += j) {
//            j = 1;
//            if (arr.get(i) == maxEl) {
//                while (i + j < arr.size() && arr.get(i + j) == maxEl) {
//                    if (++j > max) max = j;
//                }
//            }
//        }
//        System.out.println(max);



        //  ЗАДАЧА С ПОИСКОМ ПО МАССИВУ

//        Scanner input = new Scanner(System.in);
//        int n = input.nextInt();
//        ArrayList<Integer> arr = new ArrayList<>();
//        for (int i = 0; i < n; ++i) {
//            arr.add(input.nextInt());
//        }
//        Collections.sort(arr);
//        //System.out.println(arr);
//        int k = input.nextInt();
//        ArrayList<Integer> res = new ArrayList<>();
//        for (int i = 0; i < k; ++i) {
//            int min = input.nextInt();
//            int max = input.nextInt();
//            int lBound = -1;
//            int rBound = arr.size();
//            while (rBound - lBound > 1) {
//                int middle = (rBound + lBound) / 2;
//                if (arr.get(middle) >= min) {
//                    rBound = middle;
//                    if (middle != 0 && arr.get(middle - 1) < min) {
//                        lBound = middle - 1;
//                        break;
//                    }
//                } else {
//                    lBound = middle;
//                }
//            }
//            int minI = lBound;
//            lBound = -1;
//            rBound = arr.size();
//            while (rBound - lBound > 1) {
//                int middle = (rBound + lBound) / 2;
//                if (arr.get(middle) <= max) {
//                    lBound = middle;
//                    if (middle != arr.size() - 1 && arr.get(middle + 1) > max) {
//                        rBound = middle + 1;
//                        break;
//                    }
//                } else {
//                    rBound = middle;
//                }
//            }
//            int maxI = rBound;
//            res.add(maxI - minI - 1);
//        }
//        for (int i : res) {
//            System.out.print(i + " ");
//        }


        // ЗАДАЧА С КРОТОМ

//        Scanner input = new Scanner(System.in);
//        int n = input.nextInt();
//        ArrayList worms = new ArrayList();
//        worms.add(input.nextInt());
//        for (int i = 1; i < n; ++i) {
//            int a = input.nextInt();
//            worms.add((int)worms.get(i - 1) + a);
//        }
//        //System.out.println(worms);
//        int k = input.nextInt();
//        ArrayList res = new ArrayList();
//        for(int i = 0; i < k; ++i) {
//            int delic = input.nextInt();
//            int lBound = 0;
//            int rBound = worms.size();
//            while(rBound - lBound > 1) {
//                int middle = (rBound + lBound) / 2;
//                if ((int)worms.get(middle) >= delic) {
//                    if ((int)worms.get(middle - 1) < delic) {
//                        lBound = middle;
//                        break;
//                    } else {
//                        rBound = middle;
//                    }
//                } else {
//                    lBound = middle;
//                }
//            }
//            res.add(lBound + 1);
//        }
//        for (int i = 0; i < res.size(); ++i) {
//            System.out.print(res.get(i) + " ");
//        }

        //ЗАДАЧА С Х А И В

//        Scanner input = new Scanner(System.in);
//        int x = input.nextInt();
//        boolean found = false;
//        for (int b = 1; b <= x; b++) {
//            for(int a = 1; a <= x; a++) {
//                if(a % b == 0 && a * b > x && a / b < x) {
//                    found = true;
//                    System.out.println(a + " " + b);
//                    break;
//                }
//                if(found) break;
//            }
//        }
//        if (!found) {
//            System.out.println(-1);
//        }

        // ЗАДАЧА ПРО ОТРЕЗКИ

//        Scanner input = new Scanner(System.in);
//        int q = input.nextInt();
//        ArrayList first = new ArrayList();
//        ArrayList sec = new ArrayList();
//        for (int i = 0; i < q; ++i) {
//            int l1 = input.nextInt();
//            int r1 = input.nextInt();
//            int l2 = input.nextInt();
//            int r2 = input.nextInt();
//            if (l1 != l2) {
//                first.add(l1);
//                sec.add(l2);
//            } else if (r1 != r2) {
//                first.add(r1);
//                sec.add(r2);
//            } else {
//                first.add(l1);
//                sec.add(r1);
//            }
//        }
//        for (int i = 0; i < q; ++i) {
//            System.out.println(first.get(i) + " " + sec.get(i));
//        }

        //ЗАДАЧА ПРО ЧЕТНОСТЬ

//        Scanner input = new Scanner(System.in);
//        int b = input.nextInt();
//        int k = input.nextInt();
//        int sum = 0;
//        for (int i = 0; i < k; ++i) {
//            int a = input.nextInt();
//            if (i == k - 1) {
//                if (a % 2 != 0) {
//                    sum += 1;
//                }
//            } else {
//                if (b % 2 != 0 && a % 2 != 0) {
//                    sum += 1;
//                }
//            }
//        }
//        if (sum % 2 == 0) {
//            System.out.println("even");
//        } else {
//            System.out.println("odd");
//        }

//        ЗАДАЧА ПРО ТРАНСФОРМАЦИЮ СУПЕРГЕРОЕВ))0

//        Scanner input = new Scanner(System.in);
//        String hero1 = input.nextLine();
//        String hero2 = input.nextLine();
//
//        if (hero1.length() != hero2.length()) {
//            System.out.println("No");
//        } else {
//            boolean check = true;
//            for(int i = 0; i < hero1.length(); i++) {
//                boolean a1 = false;
//                boolean a2 = false;
//                if (hero1.charAt(i) == 'a' || hero1.charAt(i) == 'i' || hero1.charAt(i) == 'o' ||
//                hero1.charAt(i) == 'u' || hero1.charAt(i) == 'e') {
//                    a1 = true;
//                }
//                if (hero2.charAt(i) == 'a' || hero2.charAt(i) == 'i' || hero2.charAt(i) == 'o' ||
//                        hero2.charAt(i) == 'u' || hero2.charAt(i) == 'e') {
//                    a2 = true;
//                }
//                if (a1 != a2) {
//                    System.out.println("No");
//                    check = false;
//                    break;
//                }
//            }
//            if (check) {
//                System.out.println("Yes");
//            }
//        }

//        ArrayList array = new ArrayList();
//        for (int i = 0; i < 5; i++) {
//            array.add(sth.split(" ")[i]);
//        }
//        System.out.println(array);
    }
}

// List<Integer> x = new ArrayList();

