Submission #63783256

---

Source Code Expand

/*
Author: rnishiura
Date: 25-03-08
Description: template
*/

// #define ATCODER_
#include <bits/stdc++.h>
#ifdef ATCODER_
#include <atcoder/all>
#endif
#define _GLIBCXX_DEBUG
#define rep(x, n)      for(ll x=0; x<n; x++)
#define repi(x, a, b)  for(ll x=a; x<b; x++)
#define rrep(x, n)     for(ll x=n-1; x>=0; x--)
#define rrepi(x, a, b) for(ll x=b-1; x>=a; x--)
#define SQ(z) ((z)*(z))
#define contains(x, a) ((a).find(x) != (a).end())
#define all(a) (a).begin(), (a).end()
#define sum(a)  (accumulate(all(a), 0LL))
#define mini(a) (min_element(all(a)) - (a).begin())
#define maxi(a) (max_element(all(a)) - (a).begin())
#define mine(a) (*min_element(all(a)))
#define maxe(a) (*max_element(all(a)))
#define lowb(x, a) (lower_bound(all(a), (x)) - (a).begin())
#define uppb(x, a) (upper_bound(all(a), (x)) - (a).begin())
#define divl(n, m)  ((n+m)/(m)) 
#define divle(n, m) ((n+m-1)/(m)) 
#define divse(n, m) ((n)/(m)) 
#define divs(n, m)  ((n-1)/(m)) 
#define bstoi(s)  stoi((s), nullptr, 2)
#define MOD 998244353
#define PI 3.14159265358979323846
#define inf (1LL << 61)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define POS  fi
#define COST se
#define endl '\n'
#define unordered_multiset multiset
#define TRUE 1
#define FALSE 0

#define VNAME(v) #v
#define GET_MACRO(_1,_2,_3, NAME,...) NAME
#define print(...) GET_MACRO(__VA_ARGS__, print3, print2, print1)(__VA_ARGS__)
#define debug(...) GET_MACRO(__VA_ARGS__, debug3, debug2, debug1)(__VA_ARGS__)

#define print1(z)       { cout << (z) << endl;              }
#define print2(y, z)    { cout << (y) << ' '; print1(z);     }
#define print3(x, y, z) { cout << (x) << ' '; print2(y, z); }
#define debug1(z)       { if(DEBUG) { print(VNAME(z)); print(z); } }
#define debug2(y, z)    { if(DEBUG) { print(VNAME(y), VNAME(z)); print(y, z); }    }
#define debug3(x, y, z) { if(DEBUG) { print(VNAME(x), VNAME(y), VNAME(z)); print(x, y, z); } }
#ifdef ATCODER_
using namespace atcoder;
using mint = modint998244353;
#endif

using namespace std;
using ll  = long long;
using v   = vector<ll>;
using vv  = vector<v>;
using vp  = vector<pair<ll, ll>>;
using vvp = vector<vp>;

ll modinv(ll x) {
  ll r=1, m=MOD-2;
  x %= MOD;
  while(m) {
    if(m%2) r = r*x%MOD;
    x = x*x%MOD;
    m >>= 1;
  }
  return r;
}

struct mint {
  unsigned long long val;
  mint operator+(mint b) {
    return mint{(this->val+b.val)%MOD};
  }
  mint operator-(mint b) {
    return mint{(MOD+this->val-b.val)%MOD};
  }
  mint operator*(mint b) {
    return mint{this->val*b.val%MOD};
  }
  mint operator/(mint b) {
    return mint{this->val*modinv(b.val)%MOD};
  }
  void operator+=(mint b) { *this=*this+b; }
  void operator-=(mint b) { *this=*this-b; }
  void operator*=(mint b) { *this=*this*b; }
  void operator/=(mint b) { *this=*this/b; }
};

template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
// template<typename T>             ostream& operator<<(ostream& os,  vector<bool>  v){for (auto i : v) os << (i ? 'T' : 'F') << ' '; return os;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto i : v) os << i << ' '; return os;}
template<typename T>             ostream& operator<<(ostream& os,  vector<vector<T>>  v){for (auto& i : v) os << i << endl; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> pair<T,T> operator*(pair<T,T> a,         U b){return mp(a.first*b      , a.second*b);}
template<typename T, typename U> pair<T,T> operator/(pair<T,T> a,         U b){return mp(a.first/b      , a.second/b);}
template<typename T, typename U> pair<T,T> operator%(pair<T,T> a,         U b){return mp(a.first%b      , a.second%b);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}


const string DEBUG_MESSAGE = "DEBUG MODE IS ON";
// const int DEBUG = TRUE;
const int DEBUG = FALSE;

void solve() {
  ll n; cin >> n;
  v a(n); cin >> a;

  map<ll, ll> L, R;
  ll lc=1, rc=0;
  L[a[0]] = 1;

  repi(i, 1, n) {
    R[a[i]]++;
    if(R[a[i]] == 1) rc++;
  }
  ll ans = lc+rc;

  repi(i, 1, n-1) {
    L[a[i]]++;
    if(L[a[i]] == 1) lc++;
    R[a[i]]--;
    if(R[a[i]] == 0) rc--;
    umax(ans, lc+rc);
  }

  print(ans);
  
}

int main(void) {
  debug(DEBUG_MESSAGE);

  cin.tie(nullptr); ios::sync_with_stdio(false);
  
  ll t = 1; // cin >> t;
  rep(i, t) solve();

  debug(DEBUG_MESSAGE);
}

Submission Info

Judge Result