I have checked my solution with thousands of small test cases and a python brute force solution (with n upto 100) and it has matched all of them.
Here is my C++ code. (I have added comments to the main sections of my logic)
This is my brute force python solution
And this is the test case generator
Kindly help me. Thank you! :)