#pragma GCC optimize "trapv" // Crash on onverflow. #include #include #include #include #include #include #include #include using namespace std; struct Item : public pair { Item() {} Item(int h, int i) : pair(h, i) {} int height() const { return first; } int index() const { return second; } }; struct ItemWithNext : public Item { ItemWithNext(int h, int i) : Item(h, i) {} void AddNext(Item i) { next = i; } Item next; }; struct Ratio; Ratio operator-(const Ratio &a, const Ratio &b); struct Ratio { Ratio(int64_t x) : num(x), denum(1) {} Ratio(int64_t num, int64_t denum) : num(num), denum(denum) { normalize(); } bool operator<(const Ratio &other) const { return (*this - other).num < 0; // No longer needed as the computation above fits in int64s. // return static_cast<__int128>(num) * other.denum < // static_cast<__int128>(other.num) * denum; } bool operator<=(const Ratio &other) const { return (*this - other).num <= 0; } Ratio &operator=(const Ratio &other) { num = other.num; denum = other.denum; return *this; } void normalize() { if (denum < 0) { denum = -denum; num = -num; } int64_t g = gcd(abs(num), abs(denum)); num /= g; denum /= g; } string ToString() const { if (denum == 1) return to_string(num); return to_string(num) + "/" + to_string(denum); } int64_t num; int64_t denum; }; Ratio operator+(const Ratio &a, const Ratio &b) { return Ratio(a.num * b.denum + b.num * a.denum, a.denum * b.denum); } Ratio operator-(const Ratio &a, const Ratio &b) { return Ratio(a.num * b.denum - b.num * a.denum, a.denum * b.denum); } Ratio operator*(const Ratio &a, const Ratio &b) { return Ratio(a.num * b.num, a.denum * b.denum); } Ratio operator/(const Ratio &a, const Ratio &b) { assert(b.num != 0); return Ratio(a.num * b.denum, a.denum * b.num); } Ratio ComputeView(const ItemWithNext &left, const Item &right) { Ratio x1(left.index()); Ratio h1(left.height()); Ratio x2(left.next.index()); Ratio h2(left.next.height()); Ratio h3(right.height()); // Causes int64_t overflow when doing the sum. // Ratio x_intersection = x1 * (h3 - h2) / (h1 - h2) + x2 * (h3 - h1) / (h2 - // h1); Ratio x_intersection = x1 + (x2 - x1) * (h3 - h1) / (h2 - h1); // Sanity check: assert(Ratio(x1) <= x_intersection); assert(x_intersection <= Ratio(x1) + Ratio(1)); return Ratio(right.index()) - x_intersection; } Ratio Solve(const vector &heights) { vector filtered_heights; Ratio nicest = 0; for (int i = 0; i < heights.size(); ++i) { ItemWithNext cur(heights[i], i); if (!filtered_heights.empty()) { filtered_heights.back().AddNext(cur); } while (!filtered_heights.empty() && cur.height() > filtered_heights.back().height()) { filtered_heights.pop_back(); } if (!filtered_heights.empty()) { Ratio view = ComputeView(filtered_heights.back(), cur); if (nicest < view) { nicest = view; } } filtered_heights.push_back(cur); } return nicest; } int main() { int N; cin >> N; vector heights; for (int i = 0; i < N; ++i) { int h; cin >> h; heights.push_back(h); } Ratio nicest_backwards = Solve(heights); reverse(heights.begin(), heights.end()); Ratio nicest_forwards = Solve(heights); Ratio nicest = nicest_backwards; if (nicest < nicest_forwards) { nicest = nicest_forwards; } cout << nicest.ToString() << endl; }