#include #include #include using namespace std; #define FOR(k,m,n) for(int (k)=(m);(k)<(n);(k)++) #define rep(i,n) FOR((i),0,(n)) typedef long long ll; const int INF=1e9+7; int main(){ int n; cin>>n; cout<