#include <iostream>
#include <cstdlib>
using namespace std;
const int A[] = {4, 2, 5, 3, 7, 4, 2, 6, 8, 4, 1, 10, 10, 10, 20, 11, 15, 13, 28, 99, 11 };
const int B[] = {10, 99, 20, 30, 11, 100, 150, 101, 125};
const int C[] = {10, 20, 30, 40, 5};
int find_pivot(const int a[], int n)
{
int lo = 0, hi = n-1;
for (int i=1;i<n && lo<=hi; ++i)
{
// find the low-maximum that is no greater than our
// current high-minimum.
if (a[i] > a[lo] && a[hi] >= a[i])
lo = i;
// likewise, find the hi-minimum that is not less than
// our current low-maximum.
if (a[(n-1)-i] <= a[hi] && a[lo] < a[(n-1)-i])
hi = (n-1)-i;
}
return (lo == hi || a[lo] == a[hi] ? hi : -1);
}
int main(int argc, char* argv[])
{
int n = find_pivot(A, sizeof(A)/sizeof(A[0]));
if (n >=0)
cout << "A[" << n << "] = " << A[n] << endl;
else
cout << "A has no viable pivot.";
n = find_pivot(B, sizeof(B)/sizeof(B[0]));
if (n >=0)
cout << "B[" << n << "] = " << B[n] << endl;
else
cout << "B has no viable pivot.";
n = find_pivot(C, sizeof(C)/sizeof(C[0]));
if (n >=0)
cout << "C[" << n << "] = " << C[n] << endl;
else
cout << "C has no viable pivot.";
return EXIT_SUCCESS;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGxpYj4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBBW10gPSB7NCwgMiwgNSwgMywgNywgNCwgMiwgNiwgOCwgNCwgMSwgMTAsIDEwLCAxMCwgMjAsIDExLCAxNSwgMTMsIDI4LCA5OSwgMTEgfTsKY29uc3QgaW50IEJbXSA9IHsxMCwgOTksIDIwLCAzMCwgMTEsIDEwMCwgMTUwLCAxMDEsIDEyNX07CmNvbnN0IGludCBDW10gPSB7MTAsIDIwLCAzMCwgNDAsIDV9OwoKaW50IGZpbmRfcGl2b3QoY29uc3QgaW50IGFbXSwgaW50IG4pCnsKICAgIGludCBsbyA9IDAsIGhpID0gbi0xOwogICAgZm9yIChpbnQgaT0xO2k8biAmJiBsbzw9aGk7ICsraSkKICAgIHsKICAgICAgICAvLyBmaW5kIHRoZSBsb3ctbWF4aW11bSB0aGF0IGlzIG5vIGdyZWF0ZXIgdGhhbiBvdXIKICAgICAgICAvLyAgY3VycmVudCBoaWdoLW1pbmltdW0uCiAgICAgICAgaWYgKGFbaV0gPiBhW2xvXSAmJiBhW2hpXSA+PSBhW2ldKQogICAgICAgICAgICBsbyA9IGk7CiAgICAgICAgCiAgICAgICAgLy8gbGlrZXdpc2UsIGZpbmQgdGhlIGhpLW1pbmltdW0gdGhhdCBpcyBub3QgbGVzcyB0aGFuCiAgICAgICAgLy8gIG91ciBjdXJyZW50IGxvdy1tYXhpbXVtLgogICAgICAgIGlmIChhWyhuLTEpLWldIDw9IGFbaGldICYmIGFbbG9dIDwgYVsobi0xKS1pXSkKICAgICAgICAgICAgaGkgPSAobi0xKS1pOwogICAgfQogICAgcmV0dXJuIChsbyA9PSBoaSB8fCBhW2xvXSA9PSBhW2hpXSA/IGhpIDogLTEpOwp9CgppbnQgbWFpbihpbnQgYXJnYywgY2hhciogYXJndltdKQp7CiAgICBpbnQgbiA9IGZpbmRfcGl2b3QoQSwgc2l6ZW9mKEEpL3NpemVvZihBWzBdKSk7CiAgICBpZiAobiA+PTApCiAgICAgICAgY291dCA8PCAiQVsiIDw8IG4gPDwgIl0gPSAiIDw8IEFbbl0gPDwgZW5kbDsKICAgIGVsc2UKICAgICAgICBjb3V0IDw8ICJBIGhhcyBubyB2aWFibGUgcGl2b3QuIjsKCiAgICBuID0gZmluZF9waXZvdChCLCBzaXplb2YoQikvc2l6ZW9mKEJbMF0pKTsKICAgIGlmIChuID49MCkKICAgICAgICBjb3V0IDw8ICJCWyIgPDwgbiA8PCAiXSA9ICIgPDwgQltuXSA8PCBlbmRsOwogICAgZWxzZQogICAgICAgIGNvdXQgPDwgIkIgaGFzIG5vIHZpYWJsZSBwaXZvdC4iOwoKICAgIG4gPSBmaW5kX3Bpdm90KEMsIHNpemVvZihDKS9zaXplb2YoQ1swXSkpOwogICAgaWYgKG4gPj0wKQogICAgICAgIGNvdXQgPDwgIkNbIiA8PCBuIDw8ICJdID0gIiA8PCBDW25dIDw8IGVuZGw7CiAgICBlbHNlCiAgICAgICAgY291dCA8PCAiQyBoYXMgbm8gdmlhYmxlIHBpdm90LiI7CgogICAgcmV0dXJuIEVYSVRfU1VDQ0VTUzsKfQ==