#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define fi first
#define sc second
#define BIT(x, i) ((x >> i) & 1)
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define DKhoi signed main()
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define file ""
const int N = 1e6+5;
const int LOG = 20;
const int MOD = 1e9+7;
/// _____ _ __ _ _ ____ _____
/// | __ \ | |/ / | | | | / __ \ |_ _|
/// | | | | | ' / | |__| | | | | | | |
/// | | | | | < | __ | | | | | | |
/// | |__| | | . \ | | | | | |__| | _| |_
/// |_____/ |_|\_\ |_| |_| \____/ |_____|
/// TIEN GIANG HIGHSCHOOL FOR THE GIFTED (24-27)
int n;
int a[N], f[N];
DKhoi {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen(file".inp", "r", stdin);
freopen(file".out", "w", stdout);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgdWxsIHVuc2lnbmVkIGxvbmcgbG9uZwojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIHBpaSBwYWlyPGludCwgaW50PgojZGVmaW5lIHBsbCBwYWlyPGxvbmcgbG9uZywgbG9uZyBsb25nPgojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Mgc2Vjb25kCiNkZWZpbmUgQklUKHgsIGkpICgoeCA+PiBpKSAmIDEpCiNkZWZpbmUgZWIoeCkgZW1wbGFjZV9iYWNrKHgpCiNkZWZpbmUgcGIoeCkgcHVzaF9iYWNrKHgpCiNkZWZpbmUgcGYoeCkgcHVzaF9mcm9udCh4KQojZGVmaW5lIERLaG9pIHNpZ25lZCBtYWluKCkKI2RlZmluZSBGT1IoaSwgYSwgYikgZm9yKGludCBpID0gYTsgaSA8PSBiOyBpKyspCiNkZWZpbmUgRk9SRChpLCBhLCBiKSBmb3IgKGludCBpID0gYTsgaSA+PSBiOyBpLS0pCiNkZWZpbmUgZmlsZSAiIgoKY29uc3QgaW50IE4gPSAxZTYrNTsKY29uc3QgaW50IExPRyA9IDIwOwpjb25zdCBpbnQgTU9EID0gMWU5Kzc7CgovLy8gICAgICBfX19fXyAgICBfICBfXyAgXyAgICBfICAgIF9fX18gICAgX19fX18KLy8vICAgICB8ICBfXyBcICB8IHwvIC8gfCB8ICB8IHwgIC8gX18gXCAgfF8gICBffAovLy8gICAgIHwgfCAgfCB8IHwgJyAvICB8IHxfX3wgfCB8IHwgIHwgfCAgIHwgfAovLy8gICAgIHwgfCAgfCB8IHwgIDwgICB8ICBfXyAgfCB8IHwgIHwgfCAgIHwgfAovLy8gICAgIHwgfF9ffCB8IHwgLiBcICB8IHwgIHwgfCB8IHxfX3wgfCAgX3wgfF8KLy8vICAgICB8X19fX18vICB8X3xcX1wgfF98ICB8X3wgIFxfX19fLyAgfF9fX19ffAovLy8gICAgIFRJRU4gR0lBTkcgSElHSFNDSE9PTCBGT1IgVEhFIEdJRlRFRCAoMjQtMjcpCgppbnQgbjsKaW50IGFbTl0sIGZbTl07CgpES2hvaSB7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOyAgIGNpbi50aWUoMCk7IGNvdXQudGllKDApOwogICAgZnJlb3BlbihmaWxlIi5pbnAiLCAiciIsIHN0ZGluKTsKICAgIGZyZW9wZW4oZmlsZSIub3V0IiwgInciLCBzdGRvdXQpOwogICAgCiAgICByZXR1cm4gMDsKfQo=