#include #define rep(var,cnt) for(int (var)=0; (var)<(int)(cnt); ++(var)) #define Rep(var,init,cnt) for(int (var)=(init); (var)<(cnt); ++(var)) #define REP(var,init,cnt) for(int (var)=(init); (var)<=(cnt); ++(var)) #define ran(var,vec) for(auto &(var):(vec)) #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define SORT(v) sort(all(v)) #define RSORT(v) sort(rall(v)) #define SUM(v) accumulate(all(v),0) #define tget(tp,idx) get(tp) #define TF(flag) (flag)?1:0 using namespace std; using ll = long long; using ull = unsigned long long; using pi = pair; using pl = pair; using ti = tuple; using tl = tuple; template using vec = vector; template using mat = vector>; template using cub = vector>; template using val = valarray; template using pq = priority_queue; template using rpq = priority_queue,greater>; template ostream &operator<<(ostream &os, const pair &p){ os<<"P("< istream &operator>>(istream &is, pair &p){ is>>p.first>>p.second; return is; } template ostream &operator<<(ostream &os, const vector &v){ cout<<"V{"; for(int i=0; i<(int)v.size(); ++i){ os< istream &operator>>(istream &is, vector &v){ for(T &in:v) is>>in; return is; } template ostream &operator<<(ostream &os, const valarray &v){ cout<<"V{"; for(int i=0; i<(int)v.size(); ++i){ os< istream &operator>>(istream &is, valarray &v){ for(T &in:v) is>>in; return is; } // Usual Template End ================================================ template< typename T > struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template< typename T > using Edges = vector< edge< T > >; template< typename T > using WeightedGraph = vector< Edges< T > >; using UnWeightedGraph = vector< vector< int > >; template< typename T > using Matrix = vector< vector< T > >; template< typename G > struct CentroidDecomposition { const G &g; vector< int > sub; vector< vector< int > > belong; vector< bool > v; CentroidDecomposition()=default; CentroidDecomposition(const G &g) : g(g), sub(g.size()), v(g.size()), belong(g.size()) {} inline int build_dfs(int idx, int par) { sub[idx] = 1; for(auto &to : g[idx]) { if(to == par || v[to]) continue; sub[idx] += build_dfs(to, idx); } return sub[idx]; } inline int search_centroid(int idx, int par, const int mid) { for(auto &to : g[idx]) { if(to == par || v[to]) continue; if(sub[to] > mid) return search_centroid(to, idx, mid); } return idx; } inline void belong_dfs(int idx, int par, int centroid) { belong[idx].emplace_back(centroid); for(auto &to : g[idx]) { if(to == par || v[to]) continue; belong_dfs(to, idx, centroid); } } inline int build(UnWeightedGraph &t, int idx) { int centroid = search_centroid(idx, -1, build_dfs(idx, -1) / 2); v[centroid] = true; belong_dfs(centroid, -1, centroid); for(auto &to : g[centroid]) { if(!v[to]) t[centroid].emplace_back(build(t, to)); } v[centroid] = false; return centroid; } inline int build(UnWeightedGraph &t) { t.resize(g.size()); return build(t, 0); } }; struct UnionFind { vector< int > data; UnionFind(int sz) { data.assign(sz, -1); } bool unite(int x, int y) { x = find(x), y = find(y); if(x == y) return (false); if(data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return (true); } int find(int k) { if(data[k] < 0) return (k); return (data[k] = find(data[k])); } int size(int k) { return (-data[find(k)]); } }; vector< int > dijkstra(UnWeightedGraph &g, int s) { const auto INF = numeric_limits< int >::max(); vector< int > dist(g.size(), INF); using Pi = pair< int, int >; priority_queue< Pi, vector< Pi >, greater< Pi > > que; dist[s] = 0; que.emplace(dist[s], s); while(!que.empty()) { int cost; int idx; tie(cost, idx) = que.top(); que.pop(); if(dist[idx] < cost) continue; for(auto &e : g[idx]) { auto next_cost = cost + 1; if(dist[e] <= next_cost) continue; dist[e] = next_cost; que.emplace(dist[e], e); } } return dist; } // Template End ====================================================== constexpr int MOD=1e9+7; constexpr int INF=INT_MAX; int main(void){ int N; cin>>N; vec a(N); cin>>a; if(N==1){cout<<1< za(N,false),zb(N,false); za[0]=true,zb[1]=true; for(int i=1; i