#include #define PB push_back #define MP make_pair #define REP(i,n) for (int i=0;i<(n);i++) #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define ALL(a) (a).begin(),(a).end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P; const int INF=1e9; const int MOD=100000; int B=1000000; int main(){ int n; cin>>n; cout<