#include using namespace std; using ll=long long; using dll=long double; using pq=priority_queue,greater>; using graph=vector>; #define int ll #define double dll #define sbt(x) (x).begin(),(x).end() #define gyaku(x) reverse(sbt(x)) #define vset(x) x.erase(unique(x.begin(),x.end()),x.end()) #define so(x) sort(x.begin(),x.end()) typedef unsigned long long ull; const ll mod=1000000007; const ll mint=998244353; const ll INF=1LL<<60; const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}; const int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1}; const int dx4[4] = {1,0,-1,0}; const int dy4[4] = {0,1,0,-1}; template void chmax(t&a,u b){if(a void chmin(t&a,u b){if(b par,rank,siz; UnionFind(int no):par(no,-1),rank(no,0),siz(no,1){ } int root(int x){ if(par[x]==-1)return x; else return par[x]=root(par[x]); } bool issame(int x,int y){ return root(x)==root(y); } bool unite(int x,int y){ int rx=root(x),ry=root(y); if(rx==ry)return false; if(rank[rx] seg; void b(int sz){ while(size<=sz)size*=2; seg.resize(size*2,INF); } void update(int pos,int x){ pos+=size; seg[pos]=x; while(pos>=1){ pos>>=1; // mid seg[pos]=min(seg[pos*2],seg[pos*2+1]); } } int _query(int l,int r,int a,int b,int pos){ if(l<=a&&b<=r)return seg[pos]; if(r<=a||b<=l)return INF; int x=_query(l,r,a,(a+b)/2,pos*2); int y=_query(l,r,(a+b)/2,b,pos*2+1); return min(x,y); } int query(int l,int r){ return _query(l,r,0,size,1); } }; struct 光線{ 光線(){ ios::sync_with_stdio(0); cin.tie(0); cout<>n; vector v(n); for(int i=0;i>v[i]; } set st; for(int i=0;i