Iahub recently has learned Bubble Sort, an algorithm that is used to sort a permutation with n elements a1, a2, ..., an in ascending order. He is bored of this so simple algorithm, so he invents his own graph. The graph (let's call it G) initially has n vertices and 0 edges. During Bubble Sort execution, edges appear as described in the following algorithm (pseudocode). 
    
    
      
    procedure bubbleSortGraph()  
        build a graph G with n vertices and 0 edges  
        repeat  
            swapped = false  
            for i = 1 to n - 1 inclusive do:  
                if a[i] > a[i + 1] then  
                    add an undirected edge in G between a[i] and a[i + 1]  
                    swap( a[i], a[i + 1] )  
                    swapped = true  
                end if  
            end for  
        until not swapped   
        /* repeat the algorithm as long as swapped value is true. */   
    end procedure  
    

For a graph, an independent set is a set of vertices in a graph, no two of which are adjacent (so there are no edges between vertices of an independent set). A maximum independent set is an independent set which has maximum cardinality. Given the permutation, find the size of the maximum independent set of graph G, if we use such permutation as the premutation a in procedure bubbleSortGraph.

Input

The first line of the input contains an integer n (2 ≤ n ≤ 105). The next line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n).

Output

Output a single integer — the answer to the problem. 

Examples

Input

3
3 1 2


Output

2

Note

Consider the first example. Bubble sort swaps elements 3 and 1. We add edge (1, 3). Permutation is now [1, 3, 2]. Then bubble sort swaps elements 3 and 2. We add edge (2, 3). Permutation is now sorted. We have a graph with 3 vertices and 2 edges (1, 3) and (2, 3). Its maximal independent set is [1, 2].
100
36 48 92 87 28 85 42 10 44 41 39 3 79 9 14 56 1 16 46 35 93 8 82 26 100 59 60 2 96 52 13 98 70 81 71 94 54 91 17 88 33 30 19 50 18 73 65 29 78 21 61 7 99 97 45 89 57 27 76 11 49 72 84 69 43 62 4 22 75 6 66 83 38 34 86 15 40 51 37 74 67 31 20 63 77 80 12 53 5 25 58 90 68 24 64 23 95 32 55 47
 5
4 2 1 3 5
 10
1 9 8 10 2 3 4 6 5 7
 50
12 24 42 43 36 3 40 29 7 34 10 13 28 9 35 23 25 21 19 4 20 18 11 38 41 48 6 46 33 17 31 37 2 30 32 44 45 5 47 49 16 15 50 27 26 14 39 22 1 8

16
 3
 6
 13

//Archit Rai
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define sz(a) (int)(a.size())
#define all(c) (c).begin(),(c).end()
#define F first
#define S second
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define dout(n) printf("%d\n",n)
#define REP(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
//Works for forward as well as backward iteration
#define TRvi(c,it) for(vi::iterator it = (c).begin();it! = (c).end();it++)
#define MOD 1000000007
#define PI 3.14159265359
#define endl '\n'

#define TRACE

#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int > ii;
typedef vector<ii> vii;
typedef pair<int,ii > ip;
typedef pair< ii,ii > pp;
typedef map<string, int> msi;
typedef vector< vi > vvi;
typedef long long ll;
typedef pair<long long,long long> pll;
typedef vector<long long> vll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;
typedef pair<pll,pll>  ppll;
typedef priority_queue < ll , vector < ll > , greater < ll > > minheap;
typedef priority_queue < ll , vector < ll > , less < ll > > maxheap;
struct sort_pred {
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) 
    { 
        return left.second < right.second; 
    }
};
//sort(v,v+n,sort_pred())
void optimise()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long int gcd(long long int m, long long int n)
{
    if(n == 0)
        return m;
    return gcd(n, m % n);
}
ll powmod(ll a,ll b)
{
    if(b==0)return 1;
    ll x=powmod(a,b/2);
    ll y=(x*x)%MOD;
    if(b%2)
        return (a*y)%MOD;
    return y%MOD;
}
//Template ends here

int main()
{
    long long int n;
    cin>>n;
    ll a[n];
    REP(i,0,n)
        cin>>a[i];
    sort(a,a+n);
    ll cumsum[n]={0};
    REP(i,0,n)
    {
        if(i==0)
            cumsum[i]=a[i];
        else
            cumsum[i]=a[i]+cumsum[i-1];
    }
    ll diff=0;
    for(int i=n-1;i>=1;i--)
    {
        ll temp=0;
        temp=a[i]*(i);
        temp=temp-cumsum[i-1];
        diff+=2*temp;
    }
    diff+=cumsum[n-1];
    ll g;
    g=gcd(diff,n);
    diff=diff/g;
    n=n/g;
    cout<<diff<<" "<<n<<endl;
    return 0;
}
