/**
 *    author:  orzvanh14 (  )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
// i wants to take ioi
//binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define nn "\n"
#define pi pair<int, int>
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define pb push_back
#define TASK " "

#define ms(a, x) memset(a, x, sizeof(a))
#define all(a) a.begin(), a.end()
#define All(a, n) a + 1, a + 1 + n

#define LOG 19


const int INF = 1e18;
const int mod = 1e9+7;
const int N = 3e4  + 5;
int MOD = 998244353;
int bit[200000];
struct node{
	int kc, u, hk;
	bool operator<(const node& other) const {
        return kc > other.kc;
    }
};
struct edge{
	int v, w, h;
};
int n;
int a[N];
int st[4 * N];

vector<int> v;
void nhap(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        v.pb(a[i]);
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());
}
void build(int id, int l , int r){
	if(l == r){
		st[id] = a[l];
	}
	else{
		int m = (l + r) / 2;
		build(id * 2, l, m);
		build(id * 2 + 1, m + 1, r);
		st[id] = max(st[2 * id], st[2 * id + 1]);
	}
}
void update(int id, int l, int r, int i, int val){
	if(l > i || i > r) return;
	if(l == r){
		st[id] =  val;
		return;
	}
	else{
		int m  = (l + r) / 2;
		update(2 * id, l, m, i, val);
		update(2 * id + 1, m + 1, r, i, val);
		st[id] = max(st[2 * id], st[2 * id + 1]);
	}
}
int get(int id, int l, int r, int u, int v){
	int get1 = 0, get2 = 0;
	if(l > v || u > r) return -INF;
	if(l >= u && r <= v) return st[id]; // doan [l..r] nam trong doan [u...v]
	else{
		int m = (l + r) / 2;
		get1 = get(2 * id, l, m, u, v);
		get2 = get(2 * id + 1, m + 1, r , u, v);
	}
	return max(get1, get2);
}
void solve(){
//	build(1, 1, n);
    int m = v.size();
    int ans = 0;
    int kq = 0;
	for(int i = 1; i <= n; i++){
        int pos = lb(all(v), a[i]) - v.begin() + 1;
        int mx = 0;
        if(pos > 1) mx = get(1, 1, m, 1, pos - 1);
        int dp = mx + 1;
        if(ans > dp) kq=1;
        else if(ans == dp) kq++;
        ans = max(ans, dp);
        update(1, 1, m, pos, dp);
	}
	cout << kq << nn;
}
signed main() {
	// freopen("piggyback.in", "r", stdin);
	// freopen("piggyback.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    nhap();
    solve();
	return 0;

}