#include using namespace std; typedef long long ll; #define all(v) begin(v), end(v) #define FOR(i,a,b) for(int i=(a);i<(int)(b);i++) #define rep(i,b) FOR(i,0,b) const ll mod = 1e9+7; ll INF = 100000000; ll n,k,a[100010],b[100010],ans; string s; int main(){ cin>>n; cout<