#pragma GCC target ("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using ld = long double; using H = pair; using P = pair; using vi = vector; #define all(a) (a).begin(),(a).end() #define fs first #define sc second #define xx first #define yy second.first #define zz second.second #define Q(i,j,k) mkp(i,mkp(j,k)) #define rng(i,s,n) for(ll i = (s) ; i < (n) ; i++) #define rep(i,n) rng(i, 0, (n)) #define mkp make_pair #define vec vector #define pb emplace_back #define siz(a) (int)(a).size() #define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end()) #define getidx(b,i) (lower_bound(all(b),(i))-(b).begin()) #define ssp(i,n) (i==(ll)(n)-1?"\n":" ") #define ctoi(c) (int)(c-'0') #define itoc(c) (char)(c+'0') #define cyes printf("Yes\n") #define cno printf("No\n") #define cdf(n) for(int quetimes_=(n);quetimes_>0;quetimes_--) #define gcj printf("Case #%lld: ",qq123_+1) #define readv(a,n) a.resize(n,0);rep(i,(n)) a[i]=read() #define found(a,x) (a.find(x)!=a.end()) constexpr ll mod = (ll)1e9 + 7; constexpr ll Mod = 998244353; constexpr ld EPS = 1e-10; constexpr ll inf = (ll)3 * 1e18; constexpr int Inf = (ll)15 * 1e8; constexpr int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 }; templatebool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } ll read() { ll u, k = scanf("%lld", &u); return u; } string reads() { string s; cin >> s; return s; } H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; } bool ina(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; } bool ina(int t, int l, int r) { return l <= t && t < r; } ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; } ll popcount(ll x) { int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++; return sum; } template class csum { vec v; public: csum(vec& a) :v(a) { build(); } csum() {} void init(vec& a) { v = a; build(); } void build() { for (int i = 1; i < v.size(); i++) v[i] += v[i - 1]; } //[l,r] T a(int l, int r) { if (r < l) return 0; return v[r] - (l == 0 ? 0 : v[l - 1]); } //[l,r) T b(int l, int r) { return a(l, r - 1); } T a(pairt) { return a(t.first, t.second); } T b(pairt) { return b(t.first, t.second); } }; class mint { public:ll v; mint(ll v = 0) { s(v % mod + mod); } constexpr static int mod = Mod;// (ll)1e9 + 7; constexpr static int fn_ = (ll)2e6 + 5; static mint fact[fn_], comp[fn_]; mint pow(int x) const { mint b(v), c(1); while (x) { if (x & 1) c *= b; b *= b; x >>= 1; } return c; } inline mint& s(int vv) { v = vv < mod ? vv : vv - mod; return *this; } inline mint inv()const { return pow(mod - 2); } inline mint operator-()const { return mint() - *this; } inline mint& operator+=(const mint b) { return s(v + b.v); } inline mint& operator-=(const mint b) { return s(v + mod - b.v); } inline mint& operator*=(const mint b) { v = v * b.v % mod; return *this; } inline mint& operator/=(const mint b) { v = v * b.inv().v % mod; return *this; } inline mint operator+(const mint b) const { return mint(v) += b; } inline mint operator-(const mint b) const { return mint(v) -= b; } inline mint operator*(const mint b) const { return mint(v) *= b; } inline mint operator/(const mint b) const { return mint(v) /= b; } friend ostream& operator<<(ostream& os, const mint& m) { return os << m.v; } friend istream& operator>>(istream& is, mint& m) { int x; is >> x; m = mint(x); return is; } bool operator<(const mint& r)const { return v < r.v; } bool operator>(const mint& r)const { return v > r.v; } bool operator<=(const mint& r)const { return v <= r.v; } bool operator>=(const mint& r)const { return v >= r.v; } bool operator==(const mint& r)const { return v == r.v; } bool operator!=(const mint& r)const { return v != r.v; } explicit operator bool()const { return v; } explicit operator int()const { return v; } mint comb(mint k) { if (k > * this) return mint(); if (!fact[0]) combinit(); if (v >= fn_) { if (k > * this - k) k = *this - k; mint tmp(1); for (int i = v; i >= v - k.v + 1; i--) tmp *= mint(i); return tmp * comp[k.v]; } return fact[v] * comp[k.v] * comp[v - k.v]; }//nCk mint perm(mint k) { if (k > * this) return mint(); if (!fact[0]) combinit(); if (v >= fn_) { mint tmp(1); for (int i = v; i >= v - k.v + 1; i--) tmp *= mint(i); return tmp; } return fact[v] * comp[v - k.v]; }//nPk static void combinit() { fact[0] = 1; for (int i = 1; i < fn_; i++) fact[i] = fact[i - 1] * mint(i); comp[fn_ - 1] = fact[fn_ - 1].inv(); for (int i = fn_ - 2; i >= 0; i--) comp[i] = comp[i + 1] * mint(i + 1); } }; mint mint::fact[fn_], mint::comp[fn_]; //-------------------------------------------------------------- //-------------------------------------------------------------- template class LazySegmentTree { protected: using UPF = function; using QRF = function; using F = function; int n, rr; vectordat; T e; LazySegmentTree() {} LazySegmentTree(int size) { init(size); } LazySegmentTree(vector& v) { init(v); } virtual ~LazySegmentTree() {} virtual void eval(T& par, T& a,T& b) = 0; virtual T proc(const T& a, const T& b) = 0; public: void init(int size) { n = size, rr = 1; while (rr < n) rr <<= 1; dat.assign(2 * rr - 1, T()); for (int i = rr - 2; i >= 0; i--) dat[i] = proc(dat[i * 2 + 1], dat[i * 2 + 2]); } void init(vector& v) { n = v.size(), rr = 1; while (rr < n) rr <<= 1; dat.assign(2 * rr - 1, T()); for (int i = 0; i < n; i++) dat[i + rr - 1] = v[i]; for (int i = rr - 2; i >= 0; i--) dat[i] = proc(dat[i * 2 + 1], dat[i * 2 + 2]); } //one point update void set(int at, T x) { update(0, at, at + 1, 0, rr, [x](T& a) {a = x; }); } void upd(int a, int b, UPF func) { upd(0, a, b, 0, rr, func); } T qry(int a, int b) { return qry(0, a, b, 0, rr); } T get0() { return dat[0]; } //func([a,i))==true, func([a,i+1))==false int lb(int a, int b, F func) { e = T(); return lb(0, a, b, 0, rr, func, e); } //func([i,b))==true, func([i-1,b))==false int ub(int a, int b, F func) { e = T(); return ub(0, a, b, 0, rr, func, e); } private: void upd(int i, const int& a, const int& b, int l, int r, UPF& func) { if (b <= l || r <= a) return; if (a <= l && r <= b) { func(dat[i]); return; } eval(dat[i], dat[i * 2 + 1], dat[i * 2 + 2]); upd(i * 2 + 1, a, b, l, (l + r) / 2, func); upd(i * 2 + 2, a, b, (l + r) / 2, r, func); dat[i] = proc(dat[i * 2 + 1], dat[i * 2 + 2]); } T qry(int i, const int& a, const int& b, int l, int r) { if (b <= l || r <= a) return T(); if (a <= l && r <= b) return dat[i]; eval(dat[i], dat[i * 2 + 1], dat[i * 2 + 2]); return proc(qry(i * 2 + 1, a, b, l, (l + r) / 2), qry(i * 2 + 2, a, b, (l + r) / 2, r)); } int lb(int i, int a, int b, int l, int r, F& func, T& wa) { if (b <= l || r <= a) return b; if (a <= l && r <= b) { if (func(proc(wa, dat[i]))) { wa = proc(wa, dat[i]); return b; } if (r - l == 1) return l; } eval(dat[i], dat[i * 2 + 1], dat[i * 2 + 2]); int tmp = lb(i * 2 + 1, a, b, l, (l + r) / 2, func, wa); if (tmp < b) return tmp; return lb(i * 2 + 2, a, b, (l + r) / 2, r, func, wa); } int ub(int i, int a, int b, int l, int r, F& func,T& wa) { if (b <= l || r <= a) return a; if (a <= l && r <= b) { if (func(proc(dat[i], wa))) { wa = proc(dat[i], wa); return a; } if (r - l == 1) return r; } eval(dat[i], dat[i * 2 + 1], dat[i * 2 + 2]); int tmp = ub(i * 2 + 2, a, b, (l + r) / 2, r, func,wa); if (tmp > a) return tmp; return ub(i * 2 + 1, a, b, l, (l + r) / 2, func, wa); } }; template class Segtree :public LazySegmentTree { using Base = LazySegmentTree; public: Segtree() {} Segtree(int size) :Base(size) {} Segtree(vector& v) { init(v); } void init(int size) { Base::init(size); } void init(vector& v) { vectorr(v.size()); for (int i = 0; i < v.size(); i++) r[i] = T{ v[i],inf,1 }; Base::init(r); } void update(int a, int b, ll x) { Base::upd(a, b, [x](T& a) { a.val = x; a.lazy = x; }); } ll query(int a, int b) { return Base::qry(a, b).val; } private: void eval(T& par, T& a, T& b)override { /*if (par.lazy != inf) { a.val = par.lazy; a.lazy = par.lazy; b.val = par.lazy; b.lazy = par.lazy; } par.lazy = inf;*/ } T proc(const T& a, const T& b)override { return T{ a.val + b.val ,inf,a.len + b.len }; } }; struct Monoid { ll val, lazy, len; Monoid() :val(0), lazy(inf), len(1) {} Monoid(ll val, ll lazy, ll len) :val(val), lazy(lazy), len(len) {} }; int n; int a[300000][20]; signed main() { cin >> n; rep(i, n)rep(j, 10) a[i][j] = -1; a[0][0] = 0; rep(i, n) { int t = read(); rep(j, 10) { if (~a[i][j]) { chmax(a[i+1][(j + t) % 10], a[i][j] + 1); } chmax(a[i + 1][j], a[i][j]); } } cout << a[n][0] << endl; }