// https://yukicoder.me/problems/no/946
#define CIN_ONLY
#define DECIMAL_DIGITS 10
#define STATIC_MOD 1e9 + 7
#ifdef BTK
/**/
# include "Template.hpp"
/**/
#else
/**/
/* #region auto includes */
/* #region stl */
/**/
# include
# include
# include
using namespace std;
/**/
/* #endregion */
/* #region template/IncludeSTL.hpp*/
/**
* @file IncludeSTL.hpp
* @author btk
* @brief ########include####
* @version 0.1
* @date 2019-07-21
* @todo ###2#include######script#
* @copyright Copyright (c) 2019
*
*/
/* #endregion */
/* #region template/Macro.hpp*/
/**
* @file Macro.hpp
* @author btk
* @brief ######LL##
* @version 0.1
* @date 2019-07-13
*
* @copyright Copyright (c) 2019
*
*/
//! LL
using LL = long long;
/**
* @def DEBUG
* @brief ######if# ####if(0)#######
*/
/**/
# ifdef BTK
# define DEBUG if (1)
# else
# ifdef CIN_ONLY
# define FAST_IO
# endif
# define DEBUG if (0)
# endif
/**
* @def ALL(v)
* @brief
* ALL###
*/
# define ALL(v) (v).begin(), (v).end()
/**
* @def REC(ret, ...)
* @brief
* ##############
*/
# define REC(ret, ...) std::function
/**
* @def VAR_NAME(var)
* @brief ########
*/
# define VAR_NAME(var) # var
/**
* @brief
* range#####################
*/
template
inline T& unused_var(T& v) {
return v;
}
/* #endregion */
/* #region template/IO.hpp*/
/**
* @file IO.hpp
* @author btk
* @brief cin################
* @version 0.1
* @date 2019-07-13
*
* @copyright Copyright (c) 2019
*/
/**
* @brief ###############
*/
struct cww {
/**
* @brief Construct a new cww::cww object
* @details
* CIN_ONLY#######submit##cin#scanf###########
* DECIMAL_DIGITS#######double######################
*/
cww() {
# ifdef FAST_IO
ios::sync_with_stdio(false);
cin.tie(0);
# endif
# ifdef DECIMAL_DIGITS
cout << fixed;
cout << setprecision(DECIMAL_DIGITS);
# endif
}
};
//! ############
cww star;
/**
* @brief
* vector###cin#######
* @tparam T
* @param is
* @param v
* @return istream&
*/
template
std::istream& operator>>(std::istream& is, std::vector& v) {
for (auto& it : v) is >> it;
return is;
}
/* #endregion */
/* #region template/Loop.hpp*/
/**
* @file Loop.hpp
* @author btk
* @brief range##########
* @version 0.1
* @date 2019-07-13
*
* @copyright Copyright (c) 2019
*
*/
/**
* @brief
* range#############
* @details
* #######[bg,ed)#####
* @see range
*/
class reverse_range {
private:
struct I {
int x;
int operator*() { return x - 1; }
bool operator!=(I& lhs) { return x > lhs.x; }
void operator++() { --x; }
};
I i, n;
public:
/**
* @brief Construct a new reverse range object
*
* @param n
*/
reverse_range(int n) : i({0}), n({n}) {}
/**
* @brief Construct a new reverse range object
*
* @param i
* @param n
*/
reverse_range(int i, int n) : i({i}), n({n}) {}
/**
* @brief
* begin iterator
* @return I&
*/
I& begin() { return n; }
/**
* @brief
* end iterator
* @return I&
*/
I& end() { return i; }
};
/**
* @brief
* python #### range-based for ###
* @details
* #######[bg,ed)#####
* !############## (reverse_range)
* ######O(1)
* ####################unused_var###############
*/
class range {
private:
struct I {
int x;
int operator*() { return x; }
bool operator!=(I& lhs) { return x < lhs.x; }
void operator++() { ++x; }
};
I i, n;
public:
/**
* @brief Construct a new range object
*
* @param n
*/
range(int n) : i({0}), n({n}) {}
/**
* @brief Construct a new range object
*
* @param i
* @param n
*/
range(int i, int n) : i({i}), n({n}) {}
/**
* @brief
* begin iterator
* @return I&
*/
I& begin() { return i; }
/**
* @brief
* end iterator
* @return I&
*/
I& end() { return n; }
/**
* @brief
* ########range(reverse_range######s)
* @return reverse_range
*/
reverse_range operator!() { return reverse_range(*i, *n); }
};
/* #endregion */
/* #region template/MinMaxOperation.hpp*/
/**
* @file MinMaxOperation.hpp
* @author btk
* @brief ############
* @version 0.1
* @date 2019-07-04
*
* @copyright Copyright (c) 2019
*
*/
/**
* @brief 2########
*
* @tparam T
*/
template
struct min_op {
/**
* @brief ##
*
* @param l
* @param r
* @return T
*/
static T exec(const T l, const T r) { return l < r ? l : r; }
};
/**
* @brief 2########
*
* @tparam T
*/
template
struct max_op {
/**
* @brief ##
*
* @param l
* @param r
* @return T
*/
static T exec(const T l, const T r) { return l > r ? l : r; }
};
/**
* @brief ###########
*
* @tparam F ####
* @tparam T
* @param v
* @return T
*/
template
inline T multi_op(T&& v) {
return v;
}
/**
* @brief ###############
*
* @tparam F
* @tparam T
* @tparam Ts
* @param head
* @param tail
* @return T
*/
template
inline T multi_op(const T head, Ts&&... tail) {
return F::exec(head, multi_op(tail...));
}
/**
* @brief #######
* @see multi_op
* @tparam T
* @tparam Ts
* @param head
* @param tail
* @return T
*/
template
inline T multi_min(T&& head, Ts&&... tail) {
return multi_op>(head, tail...);
}
/**
* @brief #######
* @see multi_op
* @tparam T
* @tparam Ts
* @param head
* @param tail
* @return T
*/
template
inline T multi_max(T&& head, Ts&&... tail) {
return multi_op>(head, tail...);
}
/**
* @brief
* #####F####################
* @tparam F
* @tparam T
* @tparam Ts
* @param target
* @param candidates
* @return true
* @return false
*/
template
inline bool ch_op(T& target, Ts&&... candidates) {
const T old = target;
target = multi_op(target, candidates...);
return old != target;
}
/**
* @brief change min
* @tparam T #
* @param target #####
* @param candidates
* @return ######true
*/
template
inline bool chmin(T& target, Ts&&... candidates) {
return ch_op>(target, candidates...);
}
/**
* @brief chmin#max#
* @see chmin
* @tparam T #
* @param target #####
* @param candidates
* @return ######true
*/
template
inline bool chmax(T& target, Ts&&... candidates) {
return ch_op>(target, candidates...);
}
/* #endregion */
/* #region template/Random.hpp*/
/**
* @file Random.hpp
* @author btk
* @brief #####
* @version 0.1
* @date 2019-07-13
* @copyright Copyright (c) 2019
*/
//! ############ID#####
const pid_t pid = getpid();
/**
* @brief XorShift32###
*/
class XorShift32 {
private:
//! XorShift#####
unsigned value;
/**
* @brief XorShift32############ value ###
*/
inline void update() {
value = value ^ (value << 13);
value = value ^ (value >> 17);
value = value ^ (value << 5);
}
/**
* @brief ##############
* @return unsigned ###### value ####
*/
inline unsigned get() {
unsigned v = value;
update();
return v;
}
public:
/**
* @brief [0, 2^bit) ############
* @tparam ######31
* @return int
*/
template
inline int next_int() {
return (int)(get() >> (32 - bit));
}
/**
* @brief [-2^bit,2^bit)############
* @tparam ######31
* @return int
*/
template
inline int next_signed() {
unsigned v = get();
return (int)((v >> (31 - bit)) - (1 << (bit)));
}
/**
* @brief next_int############
* @tparam 31
* @return int
*/
template
inline int range_max() {
return (int)((1u << bit) - 1);
};
/**
* @brief Construct a new XorShift32 object
* @param seed
* @details ######value###XorShift32##########
*/
XorShift32(const unsigned seed) {
value = seed;
update();
}
/**
* @brief Construct a new XorShift 32 object
* @details ##########ID###XorShift32##########
*/
XorShift32() : XorShift32(pid) {}
};
/* #endregion */
/* #region Template.hpp*/
/**
* @file Template.hpp
* @brief ################
* @author btk15049
* @date 2019/05/02
*/
/* #endregion */
/* #endregion */
/**/
#endif
int main() {
/* write here */
int n;
cin >> n;
vector