One goes up, the other comes down Introduction

In this challenge, your task is to decide whether a given sequence of numbers can be separated into two subsequences, one of which is increasing, and the other decreasing.
As an example, consider the sequence 8 3 5 5 4 12 3.
It can be broken into two subsequences as follows:

  3 5 5   12
8       4    3


The subsequence on the first row is increasing, and the one on the second row is decreasing.
Furthermore, you should perform this task efficiently.

Input

Your input is a non-empty list L of integers in the range 0 &ndash; 99999 inclusive.
It is given in the native format of your language, or simply delimited by spaces.

Output

Your output is a truthy value if L can be broken into an increasing and a decreasing subsequence, and a falsy value otherwise.
The subsequences need not be strictly increasing or decreasing, and either of them may be empty.

Rules and bonuses

You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
Furthermore, brute forcing is forbidden in this challenge: your program must run in polynomial time in the length of the input.

You are not required to actually return the two subsequences, but there is a bonus of -20% for doing so.
To make the bonus easier to claim in statically typed languages, it is acceptable to return a pair of empty lists for the falsy instances.

Test cases

Given in the format input -&gt; None for falsy inputs and input -&gt; inc dec for truthy inputs.
Only one possible pair of subsequences is given here; there may be more.

[4,9,2,8,3,7,4,6,5] -&gt; None
[0,99999,23423,5252,27658,8671,43245,53900,22339] -&gt; None
[10,20,30,20,32,40,31,40,50] -&gt; None
[49,844,177,974,654,203,65,493,844,767,304,353,415,425,857,207,871,823,768,110,400,710,35,37,88,587,254,680,454,240,316,47,964,953,345,644,582,704,373,36,114,224,45,354,172,671,977,85,127,341,268,506,455,6,677,438,690,309,270,567,11,16,725,38,700,611,194,246,34,677,50,660,135,233,462,777,48,709,799,929,600,297,98,39,750,606,859,46,839,51,601,499,176,610,388,358,790,948,583,39] -&gt; None
[0,1,2,3,4] -&gt; [0,1,2,3,4] []
[4,3,2,1,0] -&gt; [] [4,3,2,1,0]
[1,9,2,8,3,7,4,6,5] -&gt; [1,2,3,4,6] [9,8,7,5]
[71414,19876,23423,54252,27658,48671,43245,53900,22339] -&gt; [19876,23423,27658,48671,53900] [71414,54252,43245,22339]
[10,20,30,20,30,40,30,40,50] -&gt; [10,20,20,30,40,40,50] [30,30]
[0,3,7,13,65,87,112,43,22,1] -&gt; [0,3,7,13,65,87,112] [43,22,1]
[7,4,4,7,4,7,7,4,7,4,4,4,7,7] -&gt; [7,7,7,7,7,7,7] [4,4,4,4,4,4,4]
[7,997,991,957,956,952,7,8,21,924,21,923,22,38,42,44,920,49,58,67,71,83,84,85,917,89,907,896,878,878,90,861,115,860,125,128,140,148,858,155,160,836,164,182,826,191,824,805,195,792,205,782,206,210,769,213,756,748,214,745,724,701,234,241,693,268,685,293,679,297,334,671,336,669,341,652,356,648,362,364,370,375,386,630,622,388,389,618,398,408,468,615,470,533,611,539,544,609,586,582,572,565,547,602,536,619,624,528,512,631,640,649,669,671,677,505,678,723,743,489,489,473,454,757,446,445,758,759,764,445,431,770,429,426,418,409,790,383,379,366,363,791,358,795,809,827,835,356,353,841,844,333,867,323,317,879,311,881,309,896,282,281,897,263,904,237,236,226,202,195,914,186,177,917,920,157,926,936,154,138,943,131,945,100,98,947,957,964,95,973,989,57,43,32,21,16,13,11,8,0] -&gt; [7,7,8,21,21,22,38,42,44,49,58,67,71,83,84,85,89,90,115,125,128,140,148,155,160,164,182,191,195,205,206,210,213,214,234,241,268,293,297,334,336,341,356,362,364,370,375,386,388,389,398,408,468,470,533,539,544,586,602,619,624,631,640,649,669,671,677,678,723,743,757,758,759,764,770,790,791,795,809,827,835,841,844,867,879,881,896,897,904,914,917,920,926,936,943,945,947,957,964,973,989] [997,991,957,956,952,924,923,920,917,907,896,878,878,861,860,858,836,826,824,805,792,782,769,756,748,745,724,701,693,685,679,671,669,652,648,630,622,618,615,611,609,582,572,565,547,536,528,512,505,489,489,473,454,446,445,445,431,429,426,418,409,383,379,366,363,358,356,353,333,323,317,311,309,282,281,263,237,236,226,202,195,186,177,157,154,138,131,100,98,95,57,43,32,21,16,13,11,8,0]
Pyth, 34 bytes

.N|!N|&amp;ghNT:tNhNY&amp;gYhN:tNThN:QZ^T5


Test Suite

Uses memoized recursion to keep the runtime down. Defines a 3 input function :, which takes inputs `list suffix, end of increasing sequence, end of decreasing sequence.