Chef's Chaotic Cookbook

Chef is known for his innovative and unconventional cooking techniques. He believes that the secret to creating the most delicious dishes lies in the chaos of his ingredients. To test this theory, he devised a peculiar way of arranging his cookbook.

Problem Statement

Chef has N recipes, each assigned a unique "deliciousness score" from 1 to 10^9. He wants to arrange these recipes in his cookbook to maximize what he calls the "Chaotic Deliciousness Density."

A chaotic pair in the cookbook is any pair of recipes where a less delicious recipe appears after a more delicious one. The Chaotic Deliciousness Density is calculated as the ratio of the number of chaotic pairs to the total number of recipes in the arrangement.

Chef wants to find the longest possible arrangement of recipes that maximizes the Chaotic Deliciousness Density. He believes this will lead to the most innovative and delicious meal combinations.

Input Format

• The first line contains an integer N — the total number of recipes.
• The second line contains N space-separated integers A[1], A[2], ..., A[N], where A[i] is the deliciousness score of the i-th recipe.

Output Format

• A single integer representing the maximum number of recipes that can be included in the cookbook while maintaining the highest Chaotic Deliciousness Density.

Constraints

• 1 <= N <= 10^5
• 1 <= A[i] <= 10^9

Example

Input

5  
5 4 3 2 1  

Output

5  

Explanation

In this case, including all 5 recipes in the given order maximizes the Chaotic Deliciousness Density.
There are 10 chaotic pairs in total (every pair of recipes forms a chaotic pair), resulting in a density of 10/5 = 2, which is the highest possible.

---

Optimized Solution (O(N log N))

import bisect

def longest_strictly_decreasing_subsequence(A):
    lds = []
    for x in A:
        pos = bisect.bisect_right(lds, -x)
        if pos < len(lds):
            lds[pos] = -x
        else:
            lds.append(-x)
    return len(lds)

N = int(input())
A = list(map(int, input().split()))
print(longest_strictly_decreasing_subsequence(A))