#include <bits/stdc++.h>

//上記が使用不可な環境において
/*
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <iomanip>  //setprecsion
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <cmath>  //sin, cos, tan
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <complex>
#include <bitset>
#include <utility>
#include <functional>
*/

using namespace std;

//0~nの範囲操作
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//1~nの範囲操作
#define rrep(i, n) for (ll i = 1; i <= (n); ++i)
//stl配列を全範囲操作
#define irep(it, stl) for (auto it = stl.begin(); it != stl.end(); it++)
//n~0を後ろから範囲操作
#define drep(i, n) for (ll i = (n)-1; i >= 0; --i)
//出力後改行を
#define fin(ans) cout << (ans) << endl;
//出力後空白を
#define blank(ans) cout << (ans) << " ";
//２つの値をセットに\
sort -> p -> q
#define mp(p, q) make_pair(p, q)
//３つ以上の値をセットに(3より多いときはカッコ内を増やす)\
sort -> p -> q -> r
#define mt(p, q, r) make_tuple(p, q, r)
//配列の末尾にnを追加
#define pb(n) push_back(n)
//配列の末尾を削除1
#define cb(n) pop_back(n)
//配列全操作
#define all(a) a.begin(), a.end()
//bit表示
#define BIT(n) bitset<10>(n)

typedef long long ll;
typedef long long lli;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<ll> vll;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<ll, str>> vpls;
typedef vector<tuple<str, ll, ll>> vtsl;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;

// modint: mod 計算を int を扱うように扱える構造体
template <ll MOD>
struct Fp
{
  ll val;
  constexpr Fp(ll v = 0) noexcept : val(v % MOD)
  {
    if (val < 0)
      val += MOD;
  }
  constexpr ll getmod() { return MOD; }
  constexpr Fp operator-() const noexcept
  {
    return val ? MOD - val : 0;
  }
  constexpr Fp operator+(const Fp &r) const noexcept { return Fp(*this) += r; }
  constexpr Fp operator-(const Fp &r) const noexcept { return Fp(*this) -= r; }
  constexpr Fp operator*(const Fp &r) const noexcept { return Fp(*this) *= r; }
  constexpr Fp operator/(const Fp &r) const noexcept { return Fp(*this) /= r; }
  constexpr Fp &operator+=(const Fp &r) noexcept
  {
    val += r.val;
    if (val >= MOD)
      val -= MOD;
    return *this;
  }
  constexpr Fp &operator-=(const Fp &r) noexcept
  {
    val -= r.val;
    if (val < 0)
      val += MOD;
    return *this;
  }
  constexpr Fp &operator*=(const Fp &r) noexcept
  {
    val = val * r.val % MOD;
    return *this;
  }
  constexpr Fp &operator/=(const Fp &r) noexcept
  {
    ll a = r.val, b = MOD, u = 1, v = 0;
    while (b)
    {
      ll t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    val = val * u % MOD;
    if (val < 0)
      val += MOD;
    return *this;
  }
  constexpr bool operator==(const Fp &r) const noexcept
  {
    return this->val == r.val;
  }
  constexpr bool operator!=(const Fp &r) const noexcept
  {
    return this->val != r.val;
  }
  friend constexpr ostream &operator<<(ostream &os, const Fp<MOD> &x) noexcept
  {
    return os << x.val;
  }
  friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, ll n) noexcept
  {
    if (n == 0)
      return 1;
    auto t = modpow(a, n / 2);
    t = t * t;
    if (n & 1)
      t = t * a;
    return t;
  }
};

const ll MOD = 1000000007;
using mll = Fp<MOD>;

const ll INF = INT_MAX;
const ll LLINF = 1LL << 60;
const ld EPS = 1e-9;
ll dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
ll dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

//グラフを使う際
using Graph = vector<vector<ll>>;
//(a -> b)  G[a].push_back(b);
// 無向グラフの場合は以下を追加
// G[b].push_back(a);

//厚みのあるグラフを使う際
struct Edge
{
  ll to;     // 辺の行き先
  ll weight; // 辺の重み
  Edge(ll t, ll w) : to(t), weight(w) {}
};

using Edge_Graph = vector<vector<Edge>>;

//(a -> b)(厚み weight)  G[a].push_back(Edge(b, weight));
// 無向グラフの場合は以下を追加
// G[b].push_back(Edge(a, weight));

// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v)
{
  seen[v] = true; // v を訪問済にする

  // v から行ける各頂点 next_v について
  for (auto next_v : G[v])
  {
    if (seen[next_v])
      continue;     // next_v が探索済だったらスルー
    dfs(G, next_v); // 再帰的に探索
  }
}

/*
// 頂点 0 をスタートとした探索
    seen.assign(N, false); // 全頂点を「未訪問」に初期化
    dfs(G, 0);
*/

//行きがけ順と帰りがけ順
/*
vector<bool> seen;
vector<int> first_order; // 行きがけ順
vector<int> last_order;  // 帰りがけ順

void dfs(const Graph &G, int v, int &first_ptr, int &last_ptr)
{
  // 行きがけ順をインクリメントしながらメモ
  first_order[v] = first_ptr++;

  seen[v] = true;
  for (auto next_v : G[v])
  {
    if (seen[next_v])
      continue;
    dfs(G, next_v, first_ptr, last_ptr);
  }

  // 帰りがけ順をインクリメントしながらメモ
  last_order[v] = last_ptr++;
}
*/

/*
// 頂点 0 をスタートとした探索
    seen.assign(N, false); // 全頂点を「未訪問」に初期化
    first_order.resize(N);
    last_order.resize(N);
    int first_ptr = 0, last_ptr = 0;
    dfs(G, 0, first_ptr, last_ptr);
*/

//タイムスタンプ
/*
void dfs(const Graph &G, int v, int& ptr) {
    // 行きがけ順をインクリメントしながらメモ
    first_order[v] = ptr++;

    seen[v] = true; 
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue;
        dfs(G, next_v, ptr);
    }

    // 帰りがけ順をインクリメントしながらメモ
    last_order[v] = ptr++;
}
*/

//配列の合計
template <typename T>
T Sum(vector<T> n, ll a = 0, ll b = 0)
{
  if (b == 0)
  {
    return (accumulate(n.begin() + a, n.end(), 0));
  }
  else
  {
    return (accumulate(n.begin() + a, n.begin() + b, 0));
  }
}
//少数時
template <>
ld Sum(vector<ld> n, ll a, ll b)
{
  if (b == 0)
  {
    return (accumulate(n.begin() + a, n.end(), 0.));
  }
  else
  {
    return (accumulate(n.begin() + a, n.begin() + b, 0.));
  }
}

//配列を昇順ソート
template <typename T>
void Sort(T &n, ll a = 0, ll b = 0)
{
  if (b == 0)
  {
    return (sort(n.begin() + a, n.end()));
  }
  else
  {
    return (sort(n.begin() + a, n.begin() + b));
  }
}

//配列を降順ソート
template <typename T>
void Down(T &n, ll a = 0, ll b = 0)
{
  if (b == 0)
  {
    return (sort(n.begin() + a, n.end(), greater<ll>()));
  }
  else
  {
    return (sort(n.begin() + a, n.begin() + b, greater<ll>()));
  }
}

//配列を反転
template <typename T>
void Reve(T &n, ll a = 0, ll b = 0)
{
  if (b == 0)
  {
    return (reverse(n.begin() + a, n.end()));
  }
  else
  {
    return (reverse(n.begin() + a, n.begin() + b));
  }
}

//配列nをmにコピー
template <typename T, typename U>
void Copy(T &n, U &m, ll a = 0, ll b = 0)
{
  copy(all(n), m.begin());
}

//小数点型に
template <typename T>
ld Cast(T n)
{
  return static_cast<ld>(n);
}

//配列入力
template <typename T>
void V(T &n)
{
  for (ll i = 0; i < n.size(); i++)
  {
    cin >> n[i];
  }
}

//２列配列入力
template <typename T, typename U>
void V2(T &n, U &m)
{
  for (ll i = 0; i < n.size(); i++)
  {
    cin >> n[i] >> m[i];
  }
}

//３列配列入力
template <typename T, typename U, typename W>
void V3(T &n, U &m, W &p)
{
  for (ll i = 0; i < n.size(); i++)
  {
    cin >> n[i] >> m[i] >> p[i];
  }
}

//２重配列入力
template <typename T>
void VV(T &n, ll size)
{
  for (ll i = 0; i < n.size(); i++)
  {
    for (ll j = 0; j < size; j++)
    {
      cin >> n[i][j];
    }
  }
}

//９０度回転
template <typename T>
void Rool(T &n, T &m, ll height, ll width)
{
  for (ll i = 0; i < width; i++)
  {
    for (ll j = 0; j < height; j++)
    {
      m[i][j] = n[height - j - 1][i];
    }
  }
}

//yes, noと表示
void yn(bool a)
{
  if (a)
    cout << "yes" << endl;
  else
    cout << "no" << endl;
}

//Yes, Noと表示
void Yn(bool a)
{
  if (a)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

//YES, NOと表示
void YN(bool a)
{
  if (a)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}

//yes, noと表示後終了
void fyn(bool a)
{
  if (a)
    cout << "yes" << endl;
  else
    cout << "no" << endl;
  exit(0);
}

//Yes, Noと表示後終了
void fYn(bool a)
{
  if (a)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  exit(0);
}

//YES, NOと表示後終了
void fYN(bool a)
{
  if (a)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  exit(0);
}

//AC, WAと表示
void AC(bool a)
{
  if (a)
    cout << "AC" << endl;
  else
    cout << "WA" << endl;
}

//AC, WAと表示後終了
void fAC(bool a)
{
  if (a)
    cout << "AC" << endl;
  else
    cout << "WA" << endl;
  exit(0);
}

//noneと表示後終了
void fnone(void)
{
  cout << "None" << endl;
  exit(0);
}

//Odd(奇数), Even(偶数)と表示後終了
void fOdd(bool a)
{
  if (a)
    cout << "Odd" << endl;
  else
    cout << "Even" << endl;
  exit(0);
}

//Possible, Impossibleと表示後終了
void Possible(bool a)
{
  if (a)
    cout << "Possible" << endl;
  else
    cout << "Impossible" << endl;
  exit(0);
}

//POSSIBLE, IMPOSSIBLEと表示後終了
void POSSIBLE(bool a)
{
  if (a)
    cout << "POSSIBLE" << endl;
  else
    cout << "IMPOSSIBLE" << endl;
  exit(0);
}

//四角　表示文字 a 縦幅 h 横幅 w
void square(char a, ll h, ll w)
{
  for (ll i = 0; i < h; i++)
  {
    for (ll j = 0; j < w; j++)
    {
      cout << a;
    }
    cout << endl;
  }
}

//四角枠　外周 a 中身 b 縦幅 h 横幅 w
void yoke(char a, char b, ll h, ll w)
{
  for (ll i = 0; i < h; i++)
  {
    for (ll j = 0; j < w; j++)
    {
      if (i == 0 || i == h - 1)
        cout << a;
      else if (j == 0 || j == w - 1)
        cout << a;
      else
        cout << b;
    }
    cout << endl;
  }
}

//四捨五入
ll C45(ld n)
{
  return round(n);
}

//切り上げ (a / b)時
ll Up(ll a, ll b)
{
  return ((a + b - 1) / b);
}

//素数
bool IsPrime(ll num)
{
  if (num < 2)
    return false;
  else if (num == 2)
    return true;
  else if (num % 2 == 0)
    return false;
  ld sqrtNum = sqrt(num);
  for (ll i = 3; i <= sqrtNum; i += 2)
  {
    if (num % i == 0)
      return false;
  }
  return true;
}

//桁数
ll GetDigit(ll num)
{
  return log10(num) + 1;
}

//各桁の和
ll KSum(ll n)
{
  ll sum = 0;
  if (n < 0)
    return 0;
  while (n > 0)
  {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

//数値反転
bool KReve(ll n)
{
  ll reverse = 0;
  ll remaind;
  ll tmp = n;
  while (tmp != 0)
  {
    remaind = tmp % 10;
    reverse = reverse * 10 + remaind;
    tmp /= 10;
  }
  if (reverse == n)
    return true;
  else
    return false;
}

//約数全列挙
vector<ll> enum_div(ll n)
{
  vector<ll> ret;
  for (ll i = 1; i * i <= n; ++i)
  {
    if (n % i == 0)
    {
      ret.push_back(i);
      if (i * i != n)
      {
        ret.push_back(n / i);
      }
    }
  }
  sort(begin(ret), end(ret));
  return ret;
}

//最大公約数
ll gcd(ll a, ll b)
{
  return b ? gcd(b, a % b) : a;
}

//複数個の最大公約数
ll ngcd(vector<ll> a)
{
  ll res;
  res = a[0];
  for (ll i = 1; i < a.size() && res != 1; i++)
  {
    res = gcd(a[i], res);
  }
  return res;
}

//最小公倍数
ll lcm(ll a, ll b)
{
  return a * b / gcd(a, b);
}

//複数個の最小公倍数
ll nlcm(vector<ll> numbers)
{
  ll res;
  res = numbers[0];
  for (ll i = 1; i < numbers.size(); i++)
  {
    res = lcm(res, numbers[i]);
  }
  return res;
}

//累乗(xのn乗%mod)
ll modpow(ll x, ll n, ll mod = MAX)
{
  ll res = 1;
  while (n > 0)
  {
    if (n & 1)
      res = res * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}

//逆数(aの逆数)
ll modinv(ll a, ll mod)
{
  ll b = mod, u = 1, v = 0;
  while (b)
  {
    ll t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= mod;
  if (u < 0)
    u += mod;
  return u;
}

// a^x ≡ b (mod. m) となる最小の正の整数 x を求める
ll modlog(ll a, ll b, ll m)
{
  a %= m, b %= m;
  // calc sqrt{M}
  ll lo = -1, hi = m;
  while (hi - lo > 1)
  {
    ll mid = (lo + hi) / 2;
    if (mid * mid >= m)
      hi = mid;
    else
      lo = mid;
  }
  ll sqrtM = hi;
  // {a^0, a^1, a^2, ..., a^sqrt(m)}
  map<ll, ll> apow;
  ll amari = 1;
  for (ll r = 0; r < sqrtM; ++r)
  {
    if (!apow.count(amari))
      apow[amari] = r;
    (amari *= a) %= m;
  }
  // check each A^p
  ll A = modpow(modinv(a, m), sqrtM, m);
  amari = b;
  for (ll q = 0; q < sqrtM; ++q)
  {
    if (apow.count(amari))
    {
      ll res = q * sqrtM + apow[amari];
      if (res > 0)
        return res;
    }
    (amari *= A) %= m;
  }
  // no solutions
  return -1;
}

//階乗
ll factorial(ll n)
{
  if (n > 0)
    return n * factorial(n - 1);
  else
    return 1;
}

//
ll Pow(ll a, ll b)
{
  ll ans = 0;
  if(b == 0)
  {
    ans = 1;
  }
  while(b)
  {
    ans += a;
  }
  return ans;
}

//順列 nPr
ll perm(ll a, ll b)
{
  return (factorial(a) / factorial(a - b));
}

//組み合わせ　nCr
ll comb(ll a, ll b)
{
  return (factorial(a) / (factorial(a - b) * factorial(b)));
}

//組み合わせ　nCr % mod
ll fac[500000], finv[500000], inv[500000];
// テーブルを作る前処理
void COMinit()
{
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++)
  {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}
// 二項係数計算
ll COM(int n, int k)
{
  if (n < k)
    return 0;
  if (n < 0 || k < 0)
    return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

//組み合わせの数を返す
ll cnt = 0;
ll func(vector<char> list, ll len, ll index)
{
  //列を格納するvector、列の長さ、インデックス番号
  // インデックス番号の文字をインデックス番号から右側の文字だけを交換してゆく

  // indexが末尾から2番目になったら末尾の二つだけを交換してそれぞれを表示する
  if (index >= len - 2)
  {
    for (ll i = 0; i < len; i++)
      cout << list[i]; // 交換する前の列を表示する
    cout << endl;

    swap(list[len - 1], list[len - 2]); //末尾の二つを交換する

    for (ll i = 0; i < len; i++)
      cout << list[i]; // 交換した後の列を表示する
    cout << endl;

    cnt += 2; // cntで組み合わせ数をカウントする
    return 0;
  }

  vector<char> list2 = list;
  func(list, len, index + 1); // index番号の文字がindex番目（つまり移動していな状態）にある列を
                              //次の再帰関数に渡す

  for (ll i = index + 1; i < len; i++)
  {
    swap(list[index], list[i]); // index番目とi番目を交換する
    func(list, len, index + 1); // 交換処理した列を次の再帰関数に渡す。index値は＋１しておく
    list = list2;
  }

  return 0;
}

//n ~ mの和
ll sigma(ll n, ll m)
{
  return ((n + m) * (m - n + 1) * 0.5);
}

//期待値
ld hope(ld a)
{
  return (sigma(1, a) / a);
}

//幅優先探索
// 各座標に格納したい情報を構造体にする
// 今回はX座標,Y座標,深さ(距離)を記述している
struct Corr
{
  ll x;
  ll y;
  ll depth;
};
queue<Corr> q;
ll bfs(vector<vector<ll>> grid)
{
  // 既に探索の場所を1，探索していなかったら0を格納する配列
  vector<vector<ll>> ispassed(grid.size(), vector<ll>(grid[0].size(), false));
  // このような記述をしておくと，この後のfor文が綺麗にかける
  ll dx[8] = {1, 0, -1, 0};
  ll dy[8] = {0, 1, 0, -1};
  while (!q.empty())
  {
    Corr now = q.front();
    q.pop();
    //今いる座標は(x,y)=(now.x, now.y)で，深さ(距離)はnow.depthである  ここで，今いる座標がゴール(探索対象)なのか判定する
    for (ll i = 0; i < 4; i++)
    {
      ll nextx = now.x + dx[i];
      ll nexty = now.y + dy[i];
      // 次に探索する場所のX座標がはみ出した時
      if (nextx >= grid[0].size())
        continue;
      if (nextx < 0)
        continue;
      // 次に探索する場所のY座標がはみ出した時
      if (nexty >= grid.size())
        continue;
      if (nexty < 0)
        continue;
      // 次に探索する場所が既に探索済みの場合
      if (ispassed[nexty][nextx])
        continue;
      ispassed[nexty][nextx] = true;
      Corr next = {nextx, nexty, now.depth + 1};
      q.push(next);
    }
  }
  //理解不可　returnの値は変更
  return 0;
}

//セグメント木
class Monoid
{
public:
  // 単位元
  ll unit;
  Monoid()
  {
    // 単位元
    unit = 0;
  }
  // 演算関数
  ll calc(ll a, ll b)
  {
    return a + b;
  }
};
class SegmentTree
{
public:
  // セグメント木の葉の要素数
  ll n;
  // セグメント木
  vector<ll> tree;
  // モノイド
  Monoid mono;
  SegmentTree(vector<ll> &v)
  {
    n = 1 << (ll)ceil(log2(v.size()));
    tree = vector<ll>(n << 1);
    for (ll i = 0; i < v.size(); i++)
    {
      update(i, v[i]);
    }
    for (ll i = v.size(); i < n; i++)
    {
      update(i, mono.unit);
    }
  }
  // k番目の値(0-indexed)をxに変更
  void update(ll k, ll x)
  {
    k += n;
    tree[k] = x;
    for (k = k >> 1; k > 0; k >>= 1)
    {
      tree[k] = mono.calc(tree[k << 1 | 0], tree[k << 1 | 1]);
    }
  }
  // [l, r)の最小値(0-indexed)を求める．
  ll query(ll l, ll r)
  {
    ll res = mono.unit;
    l += n;
    r += n;
    while (l < r)
    {
      if (l & 1)
      {
        res = mono.calc(res, tree[l++]);
      }
      if (r & 1)
      {
        res = mono.calc(res, tree[--r]);
      }
      l >>= 1;
      r >>= 1;
    }
    return res;
  }
  ll operator[](ll k)
  {
    // st[i]で添字iの要素の値を返す
    if (k - n >= 0 || k < 0)
    {
      return -INF;
    }
    return tree[tree.size() - n + k];
  }
  void show()
  {
    ll ret = 2;
    for (ll i = 1; i < 2 * n; i++)
    {
      cout << tree[i] << " ";
      if (i == ret - 1)
      {
        cout << endl;
        ret <<= 1;
      }
    }
    cout << endl;
  }
};

//点と線の最短距離
struct Point
{
  ld x;
  ld y;
};
struct LineSegment
{
  Point start;
  Point end;
};
//   @brief 線分と点の距離を計算する。
//   @param line 線分
//   @param point 点
//   @return ユークリッド距離
ld calc_dist(const LineSegment &line, const Point &point)
{
  ld x0 = point.x, y0 = point.y;
  ld x1 = line.start.x, y1 = line.start.y;
  ld x2 = line.end.x, y2 = line.end.y;
  ld a = x2 - x1;
  ld b = y2 - y1;
  ld a2 = a * a;
  ld b2 = b * b;
  ld r2 = a2 + b2;
  ld tt = -(a * (x1 - x0) + b * (y1 - y0));
  if (tt < 0)
    return sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0));
  else if (tt > r2)
    return sqrt((x2 - x0) * (x2 - x0) + (y2 - y0) * (y2 - y0));
  ld f1 = a * (y1 - y0) - b * (x1 - x0);
  return sqrt((f1 * f1) / r2);
}

//大文字->小文字(+32)
//少数はなるべく整数に

/*
[+][*] -> 毎回 ans %= mod
[-] -> if(ans < 0) ans += mod -> ans %= mod
[/] -> modinv(ans, mod) % mod //互いに素の時のみ
*/

//DP
template <class T>
inline bool chmin(T &a, T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}

//実行部
void Main()
{
  ll n; cin >> n;
  vll a(n); V(a);
  ll ki = 1;
  for(ll i = 0;i < n;i++)
  {
    if(a[i] % 2 == 1) ki *= 1;
    else ki *= 2;
  }
  fin(modpow(3, n) - ki)
  return;
}

//前処理
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  Main();
  return 0;
}

/*
//test時
  g++ test.cpp -o test;./test
*/
/*

//処理速度のテスト
  clock_t start = clock();
  //処理
  clock_t end = clock();
  const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
  fin(time)
*/

Measured memory_bytes: 256